这是一个澳洲的计算与算法案例
Problem 7.1: (Social distancing for koalas ) We are given a binary tree T with n nodes, and a number k. (You may assume that every non-leaf node has exactly 2 children.) We want to pick a subset S of k leaves that maximizes the value (S) = minu;v2S d(u; v), where d(u; v) denotes the distance between u and v, i.e., the length of the (unique) path from u to v in T.
(Intuitively, (S) represents the amount of separation” between the leaves in S.) You will design an efficient dynamic programming algorithm to solve this problem.
In the example below, one optimal subset S is shown in red, with (S) = 5. (Turn the picture upside down if you are a koala
