使用动态编程计算子集sum（背包）中子集解的数量

Question

所以我想知道如何计算背包问题的所有解决方案。也就是说，我有兴趣从一组最大尺寸为K的数字中找到可能的子集数。

例如，我们有一组大小为{3,2,5,6,7}的项目，最大大小为K = 13.所以解是{5,6,2}和{6,7}。另一方面，有两种解决方案;我希望我的动态编程算法报告有两种可能的解决方案。

Answer 1

这可以通过动态编程来完成。基本策略是建立一个记忆表d[i][j]，它使用与j相加的第一个i数来存储组合的数量。请注意，j = 0代表一组空数字。这是一个示例实现：

int countCombinations(int[] numbers, int target) {
    // d[i][j] = n means there are n combinations of the first j numbers summing to i.
    int[][] d = new int[target + 1][numbers.length + 1];

    // There is always 1 combination summing to 0, namely the empty set.
    for (int j = 0; j <= numbers.length; ++j) {
        d[0][j] = 1;
    }

    // For each total i, calculate the effect of using or omitting each number j.
    for (int i = 1; i <= target; ++i) {
        for (int j = 1; j <= numbers.length; ++j) {
            // "First j numbers" is 1-indexed, our array is 0-indexed.
            int number = numbers[j - 1];

            // Initialize value to 0.
            d[i][j] = 0;

            // How many combinations were there before considering the jth number?
            d[i][j] += d[i][j - 1];

            // How many things summed to i - number?
            if (i - number >= 0) {
                d[i][j] += d[i - number][j - 1];
            }
        }
    }

    // Return the entry in the table storing all the number combos summing to target.
    return d[target][numbers.length - 1];
}

只是添加一些谷歌关键字：这个问题也称为n个硬币的总和，没有重复到目标总和。

Answer 2

有一个动态背包解决方案用于此任务。在dp数组中，dp [i]存储其总和为“i”的子集数。在这种情况下你的答案是dp [K]。（对不起，缩进问题，我无法弄清楚如何使它正确:(）

dp[0] = 1 ;
  for( int i=0; i<N ; i++ )
      for( int j=K-a[i] ; j>=0 ; j-- )
          dp[j+a[i]] += dp[j]

Answer 3

我不认为Max的算法适用于这种情况：[0,0,1]目标为1.答案是4，但他的算法将输出1.他的算法仅适用于正整数，因为它假设一个0只能用空集实现。但是，如果数组中存在0，也可以实现。解决此问题的更强大的方法（以及更高的空间效率）是使用1D dp阵列。伪代码如下：

int[] dp = new int[target+1];
for (int num : nums) {
    for (int s = target; s >= 0; s--) {
        if (s >= num) {  // can include num
            dp[s] += dp[s-num];  
        } else {  // cannot include num (can be omitted, here for better explanation)
            dp[s] += 0;
        }
    }
}

return dp[target+1];

我在内部for循环中从目标回溯到0的原因是为了避免重复。考虑目标总和为4的示例[2,2,2]。如果从索引0进行迭代，那么当你在dp [4]（应该是[1 0 1 0 0]时，你会重复计算2）在内循环中一次迭代后的[1 0 1 0 1]）

希望这可以帮助。