问动态规划最优解

EN

从问题的措辞来看，分配给层次结构树中的某人的乐趣评分不一定大于他们在层次结构树中的后代。

然而，即使是这种情况，要知道选择最佳员工并不是最优的，请考虑一棵高度为2的树，其根为fun=10，子代为fun=1。然后，最佳解决方案是跳过贪婪的选择(根)，选择这20个子代。

在任何情况下，使用动态编程都可以找到最佳解决方案，即使父母的乐趣可能比他们的后代低。对于树中的一个节点v，让F( v )是在以v为根的子树中可以获得的最大乐趣。然后，要么选择v，在这种情况下，跳过子树，并查看以子节点为根的所有子树(取这些子树上的最大乐趣之和，并将fun (V)相加)，或者跳过v，然后您获得的最大乐趣是以v的子树为根的所有子树的最大乐趣之和。这给出了一个线性时间动态规划算法。

对于贪婪的例子，给出一个简单的反例。

    1
    |
 1--3--1
    |
    1

贪婪地选择，即首先选择3将不允许我们选择任何其他员工。但是如果我们不选择3，那么max将是4(全是1)。所以贪婪的方法是行不通的。

对于动态规划，我们可以将问题描述为选择给定子树的根。如果我们选择一个节点，那么它的子节点都不能被选中。但是，如果我们不选择节点，那么我们既可以选择子节点，也可以不选择子节点。

for all v initialize
  c(v,true) = fun(v)
  c(v,false)= 0

然后使用下面的递归来解决这个问题

weight(v,true)  = for all children sum( weight(ci,false) ) + fun(i)
weight(v,false) = for all children sum( max(weight(ci,false), weight(ci,true)))

对于根节点，答案将是max(weight(v,true),weight(v,false))。