找到n元树中最大的非相邻节点之和的算法

Question

给定一个整数n叉树，任务是找到最大子序列的和，其中约束条件是序列中任意两个数字不应共享树中的公共边缘。 例如： 1 / \ 2 5 / \ 3 4 最大的非相邻和= 3 + 4 + 5 = 12 下面是在http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent中概述的算法的错误扩展？

def max_sum(node, inc_sum, exc_sum):
    for child in node.children:
        exc_new = max(inc_sum, exc_sum)
        inc_sum = exc_sum + child.val
        exc_sum = exc_new
        inc_sum, exc_sum = max(max_sum(child, inc_sum, exc_sum),
                               max_sum(child, inc_sum, inc_sum - node.val))
    return exc_sum, inc_sum

但是我不确定在返回时交换exc_sum和inc_sum是否是实现结果的正确方法，我该如何跟踪可能导致最大总和的和，例如，在左子树中，最大和是（1 + 3 + 4），而导致最终最大和的和是（3 + 4 + 5），那么（3 + 4）应该如何跟踪？是否应将所有中间和存储在表中？

- maverickz

---

我想我不太理解这个例子 - 标记为总和术语的节点的路径应该是不相交的（没有共同的祖先但可能有根）_还是_不应该有两个这样的节点是兄弟？ - greybeard

@maverickz，你对答案满意吗？还是有疑问？ - advocateofnone

@greybeard：根据问题描述，被包含在总和中的两个节点不能共享一条边，即不能存在父子关系。 - maverickz

你的意思是一个通用图吗？ - advocateofnone

@maverickz 对于这样的问题，仅通过动态规划解决特殊图形即具有树结构的问题。如果您想要解决一般图形（可能具有循环）的问题，则无法使用此方法，因为您将无法将问题分解为子问题，因此无法通过动态规划解决。在这种情况下，我甚至怀疑解决方案的时间复杂度将是指数级别的，而不是多项式级别的（在这种情况下，您必须尝试所有选择的可能性，没有其他方法，对于大型输入非常耗时）。希望我回答了您的问题。 - advocateofnone

Answer 1

假设 dp[u][select] 存储答案：最大子序列和，没有两个节点之间有边，我们只考虑以节点 u 为根的子树（选择或不选择节点 u）。现在，您可以编写一个递归程序，其中每次递归的状态是 (u,select)，其中 u 表示正在考虑的子图的根，select 表示是否选择节点 u。因此，我们得到以下伪代码。

     /* Initialize dp[][] to be -1 for all values (u,select) */
     /* Select is 0 or 1 for false/true respectively        */

     int func(int node , int select )
     {
         if(dp[node][select] != -1)return dp[node][select];
         int ans = 0,i;

         // assuming value of node is same as node number
         if(select)ans=node;

         //edges[i] stores children of node i
         for(i=0;i<edges[node].size();i++)
         {
             if(select)ans=ans+func(edges[node][i],1-select);
             else ans=ans+max(func(edges[node][i],0),func(edges[node][i],1));
         }
         dp[node][select] = ans;
         return ans;
     }

     // from main call, root is root of tree and answer is
     // your final answer
     answer = max(func(root,0),func(root,1));

我们在递归的基础上使用了记忆化技术来降低时间复杂度。它的时间和空间复杂度均为O(V+E)。您可以在此处看到代码的工作版本Code。点击右上角的fork以运行测试用例
4 1
1 2
1 5
2 3
2 4
它会输出预期的12。
输入格式在代码的注释中指定，同时还有其他澄清说明。它是用C++编写的，但是如果您理解了代码，使用Python也不会有太大的变化。如果您对代码有任何疑问，请在评论中发布。

- advocateofnone

---

测试用例不应该是 4 1 1 2 1 5 2 3 2 4。 - maverickz

我已经指定了输入格式并提供了一个链接，您可以在其中运行您的测试用例。 - advocateofnone

抱歉，我没有意识到前两个参数是边的数量和根节点，而是认为它们也是父子节点。 - maverickz