求具有k个蓝色顶点的树的最优顶点覆盖

Question

我需要为以下问题找到一种“动态编程”的html" target="_blank">解决方案：

• 完美二叉树，T=（V，E）-（每个节点只有两个子节点，除了叶子）
  V=V（蓝色）∪ V（黑色）。V（蓝色）∩ V（黑色）=∅.

（换句话说，树中的一些顶点是蓝色的）

• 树根'r'.
• 整数k

顶点V'V的子集，它是T的顶点覆盖，并且|V'∩V（蓝色）|=k。（换句话说，覆盖V'包含k个蓝色顶点）

合法解V'的值是集合中的顶点数=|V'|。为了方便起见，我们将定义“非法律”解决方案的价值∞.

具有最小价值的解决方案。

（换句话说，最好的解决方案是一个覆盖的解决方案，它正好包含k个蓝色顶点，并且集合中的顶点数最小。）

我需要定义一个典型的子问题。（比如，如果我知道子树的值解是什么，我可以用它来找到问题的值解。）

并建议一个公式来解决它。

Answer 1

在我看来，你走对了方向！不过，我认为您必须使用一个额外的参数来告诉我们任何拾取的顶点距离当前子树的根有多远。例如，它可能只是指示我们是否拾取当前顶点，如下所示。

让乐趣（v， b， p）成为具有根v的子树的最佳大小，这样，在这个子树中，我们完全选择了b蓝色顶点，如果我们选择顶点，则p=1v或p=0如果我们不。

答案是fun（r，k，0）和fun（r，k，1）中的最小值：我们想要完整树的答案（v=r），精确地k顶点覆盖在蓝色（b=k）中，我们可以选择或不选择根。

那么，我们如何计算呢？对于叶子，fun（v，0，0）是0，fun（v，t，1）是1，其中t告诉我们顶点v是否为蓝色（1如果是，0如果否）。所有其他组合都是无效的，我们可以通过说相应的值是正无穷大来模拟它：例如，对于叶顶点v，值fun（v，3，1）=无穷大。在实现中，无穷大可以是大于任何可能答案的任何值。

对于所有内部顶点，让v为当前顶点，u和w为其子节点，我们有两个选项：选择或不选择顶点v。

假设我们选它。然后我们得到的f（v，b，1）的值是1（拾取的顶点v）加上fun（u，x，q）fun（w，y，r）的最小值，这样xy如果顶点v是黑色的，或者b-1如果是蓝色的，而q和r可以是任意的：如果我们选择顶点v，那么边v--u和v--w已经被我们的顶点覆盖了。

现在让我们不要拾取顶点v。然后我们得到的f（v，b，0）的值就是fun（u，x，1）fun（w，y，1）的最小值，这样xy=b：如果我们没有选择顶点v，那么边v--u和v--w必须被u和w覆盖。