在 n-ary 树中找到最大非相邻和的算法

Question

给定一棵 n 元整数树，任务是找到子序列的最大总和，其约束条件是序列中的任何 2 个数字都不应共享树中的公共边。例子： 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 是否是获得结果的正确方法，以及我如何跟踪可能导致最大值的总和sum，在这个例子中，左子树中的最大和是（1+3+4），而导致最终最大值的和是（3+4+5），那么应该如何跟踪（3+4）呢？是否应将所有中间金额存储在table中？

Answer 1

让我们说 dp[u][select] 存储答案：最大子序列和，没有两个节点有边，这样我们只考虑子序列以节点 u 为根的树（这样 u 是否被 selected ）。现在你可以编写一个递归程序，其中每个递归的状态是 (u,select) 其中 u 表示子图的根被考虑并且 select 意味着我们是否 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));

除了递归之外，我们还使用了记忆来减少 complexity.Its O(V+E) space 和时间。你可以在这里看到一个工作版本代码 Code。单击右上角的叉子以运行测试用例
4 1
1 2
1 5
2 3
2 4
它按预期提供输出 12。
输入格式在代码的注释中指定以及其他说明。它在 C++ 中，但如果您希望在 python 中理解代码，则不会有重大变化。如果您对代码有任何疑问，请在评论中 post。

在 n-ary 树中找到最大非相邻和的算法

Algorithm to find the maximum non-adjacent sum in n-ary tree

algorithm

tree

dynamic-programming

maximize