子集和动态规划 - 重叠子问题
Subset Sum Dynamic Programming - Overlapping SubProblems
我无法弄清楚重叠子问题的DP第一个属性在哪里适合子集和问题 .但是，我理解 最优子结构 part.While 正在执行 包含和排除 元素的递归解决方案问题在哪里重叠？
是否因为它是一个 NP 问题所以没有 DP 的两个属性。
问题的 Link 是 http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
有人可以帮忙吗我理解这一点。
我们称整组数S = {s[1], ...., s[n]}，目标值k，写f(X, t) = 1 如果有总和为 t 的 X 的子集，否则为 0。所以我们要计算的答案是f(S, k).
只要两个不同的数字子集具有相同的总和，并且该总和小于目标 k，就会出现重叠子问题。具体来说，假设有一个子集 SI = {s[i_1], ..., s[i_p]} 和一个不同的子集 SJ = {s[j_1], . .., s[j_q]}，这样 sum(SI) = sum(SJ) < k。假设w.l.o.g。索引都是有序的（即 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.
我无法弄清楚重叠子问题的DP第一个属性在哪里适合子集和问题 .但是，我理解 最优子结构 part.While 正在执行 包含和排除 元素的递归解决方案问题在哪里重叠？
是否因为它是一个 NP 问题所以没有 DP 的两个属性。
问题的 Link 是 http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
有人可以帮忙吗我理解这一点。
我们称整组数S = {s[1], ...., s[n]}，目标值k，写f(X, t) = 1 如果有总和为 t 的 X 的子集，否则为 0。所以我们要计算的答案是f(S, k).
只要两个不同的数字子集具有相同的总和，并且该总和小于目标 k，就会出现重叠子问题。具体来说，假设有一个子集 SI = {s[i_1], ..., s[i_p]} 和一个不同的子集 SJ = {s[j_1], . .., s[j_q]}，这样 sum(SI) = sum(SJ) < k。假设w.l.o.g。索引都是有序的（即 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.