CodeWa!
找到你要的答案

## Q：Finding the largest subsets of nodes in a tree subject to some constraints? |
## Q：找到一个树的最大子集的节点受到一定的限制？ |

Given a Tree like the following:
For each node there is a number(except for the root), in the example the numbers are random. If a node is taken, the next child-node of this node cannot be taken. But the child-child-node is allowed to take. So it's just not okay to take following nodes. I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken. I searched for solutions, I found the red-black-tree which is very similar but not really useful. Any ideas on this? |
给定一棵树如下：
对于每个节点有一个数字（除了根），在示例中的数字是随机的。 如果采取了节点，则不能采取该节点的下一个子节点。但允许子节点。因此，这是不好的采取以下节点。 I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken. 我寻找解决办法，我发现了红黑树非常相似，但不是真正有用的。 对此有何想法？ |

answer1： | 回答1： |

The problem you're trying to solve is called the maximum independent set problem applied to trees. As a hint, think about the following: For each complete subtree of the tree, think about the optimal solution for that subtree in two cases - the case where you include that node in the solution, and the case where you exclude that node from the solution. Use dynamic programming: work from the leaves of the tree up to the root of the tree.
Hope this helps! |
你试图解决的问题叫做应用于树的最大独立集问题。 作为提示，考虑以下内容： 树的每一个完整的子树，子树，考虑最优解在两例的情况下，你的解决方案，包括节点的情况下，和你排除从解结。 使用动态编程：从树的叶子到树的根。
希望这有助于！ |

tree binary-search-tree graph-algorithm depth-first-search breadth-first-search |