Given a rooted tree with $n$ weighted nodes and a number $1\leq k\leq n/2$, what is an efficient algorithm for finding a subset of the nodes having
- $k$ elements
- no node being an ancestor of another
- maximal sum of the weights (among all subsets fulfilling the previous two conditions)
Edit: Comments suggest dynamic programming. Here's my failing attempt in that: sort the nodes according to weight in decreasing order. The case $k=1$ is easy of course. Take the first node. But what about moving from $k$ to $k+1$? We can't just take the next weightiest node that is not an ancestor or a grandchild of any of the nodes in the previously constructed subset and add it to the subset. This could fail already in the case $k=1$. What's the correct approach here?