如何修复我的代码以编写子集总和问题解决方案的变体？

Question

考虑子集和 (SUSU) 问题，我需要编写 class 中所示解决方案的一个变体，它还将打印哪些权重被聚合以达到给定的总和。例如，如果：

sum=12;
int[] weights={1,7,9,3};

输出将是：0011 也就是说，对于权重中的每个值，如果添加了它，我们写“1”，否则写“0”。

在朋友的帮助下，我写了如下代码：

    public static void main(String[] args) {

    int[] arr={9,1,7,3};
    System.out.println(Arrays.toString(SubsetSum(arr,12)));
}   

public static int[] SubsetSum(int[] arr, int sum){
    int[] output= new int[arr.length];
    return SubsetSum(arr,sum, 0, output);
}

public static int[] SubsetSum(int[] arr, int sum, int index, int[]weights){
    int[] output= new int[arr.length];
    if(sum==0)
        return weights;
    if(sum<0 | index>=arr.length)
        return output;
    weights[index]=0;
    int[] arr1= SubsetSum(arr,sum,index+1, weights);
    weights[index]=1;
    int[]arr2=SubsetSum(arr,sum-arr[index],index+1,weights);
    boolean isZero=true;
    for(int i=0; i<arr1.length & isZero; i=i+1)
        if(arr1[i]!=0)
            isZero=true;
    if(isZero)
        return arr2;
    else
        return arr1;
}

我希望 SubsetSum(arr,12) 的输出为 [1, 0, 0, 1] 但实际输出为 [0, 0, 0, 0]。我明白为什么它 return 从我的代码输出这个，但我不知道如何修复它。

Answer 1

我改变了 return 结果的方法。现在用过的物品以 used 参数的位编码。

Ideone。

Main 打印项目的索引（或者在失败的情况下什么都不打印）- 例如 1,2,3，即 1 + 7 + 13

我不熟悉 Java，所以表示结果以便更好地查看（可能类似于 inttobinary）

public static void main(String[] args) {

    int[] arr={9,1,7,13,3};
    int i = 0;
    int res = SubsetSum(arr, 21, 0, 0);
    while (res > 0) {
        if ((res & 1) > 0) 
            System.out.println(i);
        i++;
        res >>= 1;
    }       
}   

public static int SubsetSum(int[] arr, int sum, int index, int used){
    if(sum==0)
        return used;
    if(sum<0 | index>=arr.length)
        return 0;
       int a = SubsetSum(arr,sum,index+1, used);
       int b = SubsetSum(arr,sum-arr[index],index+1, used | (1 << index));
       if (a > 0)
          return a;
       else
          return b;
}  
}

P.S。您的代码中的缺陷：
isZero 永远不会改变。
如果您将逻辑更正为 return 非零数组，它将全部填充为 1 - 可能是因为 weights[index]=1; 通过公共引用更改了相同的数组实例（不知道 Java 术语） .在我的代码中，每个递归级别都有自己的 used 实例，修改它的位不会影响其他分支中的值。

如何修复我的代码以编写子集总和问题解决方案的变体？

How to fix my code to write a variant of the solution of the SubSet Sum problem?

java

arrays

algorithm

subset-sum

array-algorithms