algorithm - 证明决策概率在 NP 中

Question

我正在阅读 CLRS，试图自学，但发现这部分很难。

我正在尝试解决，但没有真正的解决方案可供引用。

假设您有以下输入:x1, x2, x3, ..., xn m1, m1, m3, ... mn M1 and M2

然后你必须输出:A partition into two disjoint subsets S, T (so the intersection is an empty set) so that the sum of each mk (1<=k<=n) of all elements in S is <= M1 and the sum of each mk (1<=k<=n) of all elements in T is <= M2, so that the total value sum of all (xk's in S) + (xk's in T) is maximized. where (1<=k<=n)

我试图证明它在 NP 中。 我在进行动态编程时遇到了类似的问题，相信这是针对背包的。但这似乎有点复杂。我一直在草稿纸上写，但似乎无处可去。这是出于个人兴趣。

Answer 1

让我们以此作为决策版本:

Is there a partition S, T such that S and T are disjoint, the total weight of S <= M1, the total weight of T <= M2, and the total value of S∪T >= Y?

(我在那里将其改写为“重量”和“值(value)”，以使与背包的联系更加明显)

现在，这是在 NP 中吗？

是的。有几种方法可以显示 NP 的成员资格，最简单的可能是这种方式:有一个证人可以让我们验证(在多项式时间内)YES 的答案是正确的。 witness就是一对S和T，这里的验证也不需要任何技巧，只要测试问题中提到的所有条件即可。

它也是 NP 完全的，因为它将解决一个背包实例。这个问题就像有两个背包，只需将其中一个的大小设为零，它就会变回普通背包。