algorithm - 二叉树上的动态规划 : Maximize data transmitted with limited edge capacity

Question

给定一个由边容量为 c_e 的节点组成的二叉树网络。叶节点处有数据，每个节点的数据大小为s_v。 L_e 是边 e 下面的子树中所有叶子的集合。我们的目标是找到叶子的子集 S，使得传输到根 r 的数据大小数量最大化，但对于数据通过容量约束的所有边，必须保持。假设 c_e 和 s_v 是非负整数，m 是它们的最大值。在树上使用动态规划，它应该在 O(nm^2) 时间内运行。

我已经为此工作了几个小时，但还没有真正提出一个可行的解决方案。任何提示将不胜感激。

编辑:数据必须作为一个整体传输或根本不传输。例如，如果一片叶子有 10 个，则算法只能取 10 个或 0 个。

例如，

v4=1, v5=3, v6=2, v7=2. 
e1=(v1,r), e2=(v2,v1) and e3=(v3,v1) and so on. 
assume that the capacity for e4, e5,e6 and e7 satisfied. But c1=5, c2=3 and c3=4

如果我们专注于寻找每个子树的最大值，我们最终将采用 v5 和 v6+v7，这不是最优的。如何制定动态规划规则来解决这个问题并找到正确的最优解？

Answer 1

类似于子集求和的动态规划求解...

对于每个节点，计算叶子子集的可达到总和集，并且对于每个可达到的总和，记住最后一个贡献子节点和之前的总和。您可以使用此信息来重建产生总和的集合。

在对树进行后序遍历时，您可以仅使用其子节点的信息为每个节点计算该集合。

当您到达根部时，选择可达到的最大总和并重建产生它的叶子。