c - 子集和 - 二维动态规划

Question

我正在尝试查找总和为 m 的一组 n 个数字的所有 子集。例如，如果我有集合 (10,20,30,40,40,50,80) 和 m = 90 子集是 (10,80 )、(20,30,40) 和 (40,50)。我有代码可以使用类似...找到像这样的小案例

M[i, j] = max(M[i − 1, j], M[i − 1, j − A[i])

然后回溯使用...

if (M[n][m]!=0)
{
    for ( i = n; i >= 1; i --)
        if (M[i - 1][j]!=M[i][j])
        {
            printf ("Use item %d = %d\n", i, A[i]);
            j -= A[i];
        }
}

但是当我尝试更大的测试用例时，它不会返回所有子集。任何帮助将不胜感激。

Answer 1

所有正数都允许修剪，这大大降低了复杂性(虽然我不知道平均多少)。对于大型集合，您可能需要更精细的算法，但这里是:

1. 将(多)集合排序成一个数组，例如nums；例如，nums = { 10, 20, 30, 40, 40, 50, 80 }
2. 创建一个累积和数组，cum；那将是 cum = { 10, 30, 60, 100, 140, 190, 270 }

现在(C-ish 伪代码)

void parts(target, index, set){  // assuming we only want to print the sets out
    if (target == 0){
        print out set;
        return;
    }
    while(index >= 0 && nums[index] > target) --index; // skip too large numbers
    if (index < 0 || cum[index] < target) return;  // done, all numbers too large or total too small
    for(; index >= 0 && cum[index] >= target; --index){  // we can stop when the total sum is too small
        add nums[index] to set;
        parts(target - nums[index], index-1, set);
        remove nums[index] from set;
        // if no duplicate sets are desired, skip duplicates, for the example,
        // (40,50) would be created twice without skipping:
        // while(index > 0 && nums[index-1] == nums[index]) --index;
    }
}