子集和动态规划 - 重叠子问题

Question

我无法弄清楚重叠子问题的 DP 第一属性在哪里适合Subset Sum Problem。但是，我了解最佳子结构部分。在进行包含和排除元素的递归解决方案时，问题在哪里重叠？
是不是因为它是一个 NP 问题，所以不具备 DP 的两个性质？
问题的链接是http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
有人可以帮助我理解这一点吗？

Answer 1

我们将整个数字集 S = {s[1], ...., s[n]} 称为目标值 k，如果存在 X 的一个子集求和，则写 f(X, t) = 1到 t，否则为 0。所以我们要计算的答案是f(S, k)。

每当两个不同的数字子集具有相同的总和并且该总和小于目标 k 时，您就会遇到重叠子问题。具体来说，假设有一个子集 SI = {s[i_1], ..., s[i_p]} 和一个不同的子集 SJ = {s[j_1], ..., s[j_q]}，使得总和(SI) = 总和(SJ) < k。假设wlog 索引都是有序的（即a < b 意味着i_a < i_b 和j_a < j_b），并且i_1 <= j_1 （如果不是，则只需交换SI 和SJ）。然后，子问题 f({s[1], ..., s[m-1]}, k-sum(SI)) 将在（至少）通过调用树的两条不同路径中出现：从 f( S, k)（即根）并选择包含 SI 中的所有数字，并且不包含索引 >= i_1 的其他数字；从 f(S, k) 开始并选择包含 SJ 中的所有数字并且不包含索引 >= j_1 的其他数字，然后选择还排除接下来的 j_1 - i_1 数字。

工作示例

假设 S = {3, 4, 5, 6, 11} 且 k = 14。然后通过排除 11 并包括 5 和 6，我们得到子问题 f({3, 4}, 3)（这将有解 1)——这对应于选择 SI = {5, 6} 和 i_1 = 3。或者，通过包含 11，然后排除 5 和 6，我们再次得到子问题 f({3, 4 }, 3) -- 这对应于选择 SJ = {11} 和 j_1 = 5。