动态规划计算子集和（背包）中子集解的个数

Question

所以我想知道如何统计一个背包问题的所有解。也就是说，我有兴趣从一组最大大小为 K 的数字中找出可能的子集数。

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

Answer 1

这个task.In 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 2

这可以用动态规划来完成。基本策略是建立一个记忆 table、d[i][j]，它使用总和为 i 的前 j 个数字存储组合数。请注意，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];
}

只是添加一些Google关键字：此问题也称为将 n 个硬币不重复地求和到目标总和。

Answer 3

我认为 Max 的算法不适用于以下情况：目标为 1 的 [0,0,1]。答案是 4，但他的算法将输出 1。他的算法仅适用于正整数，因为它假设总和为 0 只能用空集实现。但是，如果数组中存在0也可以实现。解决这个问题的更可靠的方法（也更 space 有效）是使用一维 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] 时，您将重复计算 2（应该是 [1 0 1 0 0] [1 0 1 0 1] 在内循环中进行一次迭代后）。

希望对您有所帮助。

动态规划计算子集和（背包）中子集解的个数

Counting the number of subset solution in the subset sum (knapsack) with dynamic programming

algorithm

knapsack-problem

subset-sum