在受某些约束的情况下找到树中最大的节点子集？

Question

给定一棵如下所示的树：

            X
    /               \
    1               6
/   |   \       /   |   \   
2   5   9       1   5   3
   ...             ...

每个节点都有一个数字（根节点除外），示例中的数字是随机的。

如果取了一个节点，则不能取该节点的下一个子节点。但是child-child-node是允许带的。所以拿下面的节点就不行了

我正在寻找一种算法，该算法构建所有节点的子集，该子集具有最大数量（所有采用节点的数量总和）。 必须要扎根。

我搜索了解决方案，我发现红黑树非常相似但不是很有用。

对此有什么想法吗？

Answer 1

您要解决的问题称为 maximum independent set problem 应用于树。

作为提示，请考虑以下事项：

• 对于树的每个完整子树，在两种情况下考虑该子树的最佳解决方案 - 在解决方案中包含该节点的情况，以及从中排除该节点的情况解决方案。

• 使用动态规划：从树的叶子到树的根。

希望对您有所帮助！