子集和动态规划-重叠子问题
我无法弄清楚重叠子问题的DP第一属性在哪里适合子集和问题。然而，我理解最优子结构部分。在执行包含和排除元素的递归解决方案时，问题在哪里重叠
是不是因为这是一个NP问题，所以没有DP的两个性质
问题的链接是http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
有人能帮助我理解这一点吗。
共有1个答案
让我们将整个数字集称为S={s[1]，……， s[n]}，目标值k，如果X的子集求和为t，则写入f（X， t）=1，否则写入0。所以我们要计算的答案是f（S， k）。
只要两个不同的数子集具有相同的和，并且该和小于目标k，您就会得到重叠的子问题。详细地说，假设有一个子集SI={s[i_1]，…，s[i_p]}和另一个子集SJ={s[j_1]，..，s[j_q]}，这样sum（SI）=sum（SJ）
假设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。
-
问题链接如下： https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ 我没有看到重叠的子问题属性在问题中得到满足，至少在输入情况下是如此。例如，在下面的链接中，递归树没有任何重叠的子问题 http://www.zrzahid.com/subset-sum-problem-dynamic-programming/
-
我有一个子集问题的工作代码，如果它发现一个子集等于所需的目标，它可以打印数字。 > 我想打印给定目标的所有可能的子集，我不知道要为此更改什么。 我如何让它对负数起作用？
-
给定一组非负整数和一个值和，确定给定集合中是否有和等于给定和的子集。 例如： 我实际上用这段代码解决了问题： 然而，现在我想重建所有可能的组合，形成给定的总和。 是可以从我的回忆录矩阵中做到这一点，还是我必须以不同的方式做到这一点？
-
我正在练习动态编程，我正在努力调试我的代码。这个想法是在给定一组数字的情况下找出求和是否可能。这是我的代码： 以下是输出： 据我所知，在我的fe语句中，算法应该向上1行，然后查看x和y的差异并检查该槽是否可能。例如，在最明显的情况下，最后一行的最后一个元素。那将是10（y）-11（x），它应该一直回到它上面一行的索引1，我们知道这是True。不完全确定我做错了什么，如果能帮助理解这一点，将不胜感激
-
为了使动态规划适用，一个问题必须具有两个关键属性:最优子结构和重叠子问题[1]。对于这个问题，我们将只关注后一个属性。 重叠子问题有多种定义，其中两个是： 如果一个问题可以分解为多次重用的子问题，或者问题的递归算法一遍又一遍地解决同一个子问题，而不是总是产生新的子问题，那么问题就被称为具有重叠的子问题[2]。 要应用动态规划，优化问题必须具备的第二个要素是子问题的空间必须“小”，因为问题的递归算法
-
给定一个数组，是否可以从起始索引开始选择一组整数，这样该组就与给定的目标相加？但是，附加的限制是必须选择所有的6。 groupSum6(0,[5,6,2],8）true groupSum6(0,[5,6,2],9）false groupSum6(0,[5,6,2],7）false 只是想弄清楚我错在哪里。声明nums[start]==6的特殊情况是不是错误的方法？