dynamic-programming - 组合不相交子集的最优子结构

Question

我希望了解此问题如何显示最佳子结构：

问题：给定任何只有正整数作为节点的二叉树，你如何找到一个不相交的子集（由它们之间没有边的节点组成）来获得最大可能的乘积。

到目前为止，我已经确定，由于节点只能是正数，因此最大的乘积要么是尽可能多的节点相乘的结果，要么是选择具有较高值的节点进行相乘，要么是两者之间的某种组合. 如果我要采用第一个解决方案，我可以从最低级别开始，然后从其他级别获取节点。但是，这并没有显示出最佳的子结构。任何指针将不胜感激！

score 0 · Accepted Answer

根据Wikipedia的说法，“如果一个问题可以通过将其分解为子问题然后递归地找到子问题的最佳解决方案来优化解决，那么就说它具有最佳子结构。”

我们似乎有一个明确的案例可以将这个问题分解为子问题并递归解决。设t为函数评估的当前节点。如果我们包含t，则不能包含它的任何子代，因此我们将其值乘以孙辈的结果作为参数；否则，我们将孩子的结果作为参数相乘。一般来说：

f(t) = max(
  value(t) * product(f(g)),
  product(f(c))
)

where g is a granchild of t
      c is a child of t

score 0 · Accepted Answer

如果给定的树是自由（无根）树，则选择根R。

让我们在树T上将函数 F(R) 定义为在以R作为其元素之一的所有有效节点集合中具有最大乘积的节点集合。此处有效是指“由它们之间没有边的节点制成”。

此外，让我们在树T上定义类似于 F(R) 的函数 H(R)，但在没有R作为其元素之一的集合上。

我们可以说，一组最优节点O可以有（或没有）节点R作为其元素之一。

如果R ∈<em>O 则最优节点集O'是
{ R , H(R.children[0]), H(R.children[1]), ..., H(R.children[R .children.size() - 1])} 其中 H(R.children[i]) 是在以 R.children[i] 为根的子树上定义的。因为在O中选择了R，所以它的任何子节点都不能属于O，并且 H(R.children[i]) 中的节点乘积大于或等于O中属于由 R.children[i 定义的子树的节点的乘积]。因为每个子树的答案都独立于其他子树的答案并且O是最优的，我们知道 H(R.children[i]) 中的节点乘积低于或等于O中属于 R.children[i] 定义的子树的节点乘积。那么O'也是最优的。
如果R ∉<em>O 那么最优节点集O'是
{ R , max(F(R.children[0]), H(R.children[0])), max(F(R.children[ 1]), H(R.children[1])), ..., max(F(R.children[R.children.size() - 1]), H(R.children[R.children.size () - 1]))} 其中 F(R.children[i]) 和 H(R.children[i]) 在以 R.children[i] 为根的子树上定义。或多或少与#1 相同的解释，但由于没有在O上选择R，因此可以在其子树上选择（或不选择）任何R的孩子。

由于最优选择是未知的，因此答案是 max(F( R ), H( R ))，因为在最优集中选择R只有两种可能的情况。

2 回答 2