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

Question

我无法确定重叠子问题的DP第一属性在子集和问题中的位置。然而，我理解最优子结构部分。在递归解决包含和排除元素的过程中，问题在哪里重叠？
这是因为它是一个NP问题，所以没有DP的两个属性吗？
问题链接：http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
请有人帮助我理解这个问题。

- Art

---

我建议你不必关心这两个属性。它们既不是理解和编写动态规划解决方案的必要条件，也不是证明动态规划解决方案的必要条件。 - kraskevich

@ILoveCoding，您的意思是说即使没有这两个属性，我们也可以找到DP解决方案吗？您在Subset Sum的递归解决方案中是否看到任何重叠问题？ - Art

不需要使用这两个属性的概念（在我看来，它们并没有帮助解决问题），你可以证明这个解决方案的正确性并分析其时间复杂度。 - kraskevich

好的...那么如果我没有看到上述两个属性，我怎么知道可以在这个特定的问题中应用DP呢？ - Art

可以使用数学归纳法证明这个解决方案的正确性。 - kraskevich

Answer 1

我们将整个数字集合称为S = {s[1], ...., s[n]}，目标值为k，并写出f(X，t) = 1，如果存在一个子集X的总和等于t，否则为0。 因此，我们想要计算的答案是f(S，k)。

当两个不同的数字子集具有相同的总和且该总和小于目标k时，您将获得重叠的子问题。详细来说，假设有一个子集SI = {s[i_1]，...，s[i_p]}和一个不同的子集SJ = {s[j_1]，...，s[j_q]}，使得sum（SI）= sum（SJ） = i_1;之后，选择在从f（S，k）开始并选择包括SJ中的所有数字和没有其他数字的指数> = j_1之后，还要排除下一个j_1-i_1个数字，将出现子问题f（{s [1]，...，s [m-1]}，k-sum（SI））。

工作示例：假设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。

- j_random_hacker

---

但并不总是有重叠的子问题，对吧？只有当两个不同的数字子集具有相同的和，并且该和小于目标k时，才会发生这种情况，就像你在回答中提到的那样，对吗？@j_random_hacker 和 Raghav。此外，您能否解释一下此问题的最优子结构属性。谢谢。 - Surbhi Jain

@SurbhiJain：如果你的第一个问题是“是否存在问题实例，其中没有任何子问题被重复遇到超过一次？”，那么答案是肯定的：特别地，每当不存在两个子集给出相同的和时（例如，当S为{1, 2, 4, 8, 16, 32}时，恰好有一种方法可以使0到63之间的每个数字）。一个很好的思考方式是：画一个n×k的顶点网格，其中(i，j)处的顶点对应于子问题({s[1]，...，s[i]，j)，我将其缩写为(i，j)。现在对于每个这样的顶点(i，j)，画两个入射箭头：一个... - j_random_hacker

...从（i-1，j）中取一个，从（i-1，j-s[i]）中取一个：每个箭头代表我们需要解决的子问题，以便解决子问题（i，j）。现在想一想：当其顶点有多个出射箭头时，子问题将被重复使用。实际上，从顶点（i，j）最多可以有两个出射箭头：一个水平箭头指向（i+1，j），一个对角线箭头指向（i+1，j+s[i+1]）。前者存在于从（i+1，j）到（n，k）的路径存在时，或者等效地说，当存在一个子集{ s [i + 2]，...，s [n]}，其总和为k-j时：该子集贡献了“垂直”移动。... - j_random_hacker

后者存在的条件是从（i+1，j+s[i+1]）到（n，k）存在一条路径，或者等价地说，存在一个{s[i+2]，...，s[n]}的子集，其总和为k-(j+s[i+1])：请注意，我们可以将s[i+1]添加到该集合中，以获得第二个必然不同的S子集，其总和为k-j。因此，如果从（i，j）出发的两条边都存在，则至少有2个S子集的总和相同，即k-j。 - j_random_hacker

在那些没有重叠子问题的情况下，动态规划并不能比普通递归解决方案提供更好的改进。但在这些情况下，它与普通递归一样有效，并且在剩余的情况下可以指数级地加快速度。 - j_random_hacker