通过 DP 的子集和

Question

在 http://comproguide.blogspot.in/2013/10/subset-sum-problem.html
上有关于这种方法的简明解释然而，我通过一个小练习来列举这个算法，以找到 {1,2,3,4} 中总和为 4 的子集。

我注意到单元格 {1,1},{2,2} return 是错误的。

我是不是理解错了？
还是该算法不认为该集合是其自身的子集？

我希望 {1,1} 到 return 为真，因为 1 加起来就是它自己。

Answer 1

{1} 应该算作总和为 1 的子集。我向程序添加了一些输出以显示 table:

public class SubsetSum {
    public static void main(String[] args) {
        int [] array = { 1, 2, 3, 4 };
        hasSum(array, 4);
    }

    public static boolean hasSum(int [] array, int sum) {
        int len = array.length;
        boolean[][] table = new boolean[sum+1][len+1];
        for(int i = 0; i <= len; i++) table[0][i] = true;
        for(int i = 1; i <= sum; i++) table[i][0] = false;
        for(int i = 1; i <= sum; i++) {
            for(int j = 1; j <= len; j++) {
                table[i][j] = table[i][j-1];
                if(!table[i][j] && i >= array[j-1]) {
                    table[i][j] = table[i-array[j-1]][j-1];
                }
            }
        }

        System.out.printf("%10s ", "-");
        for(int i = 0; i <= sum; i++) {
            System.out.printf("%10s ", i);
        }
        System.out.println();
        for(int j = 0; j <= len; j++) {
            System.out.printf("%10s ", j);
            for(int i = 0; i <= sum; i++) {
                System.out.printf("%10s ", table[i][j]);
            }
            System.out.println();
        }

        return table[sum][len];
    }
}

输出：

     -          0          1          2          3          4 
     0       true      false      false      false      false 
     1       true       true      false      false      false 
     2       true       true       true       true      false 
     3       true       true       true       true       true 
     4       true       true       true       true       true

这些结果看起来是正确的。我会解释一些值，例如：

table[0][0] 为真，因为 {} 总和为 0
table[1][1] 为真，因为 {1} 总和为 1
table[2][2] 为真，因为 {2} 总和为 2
table[3][2] 为真，因为 {1,2} 总和为 3
table[4][3] 为真，因为 {1,3} 总和为 4

Answer 2

我是 post 的作者。 @fgb 显示的任何输出看起来都是正确的。我没有看到代码有任何问题。我的解释有问题吗？

通过 DP 的子集和

subset sum through DP

java

algorithm

dynamic-programming