使用动态编程找到子集和的解决方案

Question

我想做的事

我想找到一个与目标相加的数组的子集T.我还想使用动态编程方法(以及自下而上的解决方案)来做到这一点.

我现在有什么

目前我只找到一种方法来查看是否在所有大小的子集中N,是否存在至少一个具有所需总和的子集.见下面的代码.

public boolean solve(int[] numbers, int target) {

    //Safeguard against invalid parameters
    if ((target < 0) || (sum(numbers) < target)){
        return false;
    }

    boolean [][] table = new boolean [target + 1] [numbers.length + 1]  ;

    for (int i = 0; i <= numbers.length; ++i) {
        table[0][i] = true;
    }


    /* Base cases have been covered. 
     * Now look set subsets [1..n][target] to be true or false.
     * n represents the number of elements from the start that have a subset 
     * that sums to target
     */
    for (int i = 1; i <= target; ++i){
        for (int j = 1; j <= numbers.length; ++j){
            /* Mark index j as one of the numbers in the array
             *  which is part of the solution with the given subtarget */
            table [i][j] = table[i][j-1];
            if (i >= numbers[j-1])
                table[i][j] = table[i][j] || table[i - numbers[j-1]] [j-1];
        }
    }

    return table[target][numbers.length];
}

我被卡住了

现在,我知道如果有是一个解决方案,但我不能想办法实际输出的解决方案.

我不是在寻找任何人为我提供特定的代码,但我们欢迎伪代码以及如何保存解决方案的提示.

Answer 1

您提供的算法可以保持不变,除了DP表之外,您不需要存储任何其他内容table[][].您只需要一个额外的后处理阶段,您可以在其中"向后"步骤table[][]以获得解决方案集.

回忆一下:

您已经计算了表table[i][j],该表存储每个值0 <= i <= t(:= target)并且每个0 <= j <= n(:= numbers.length)表示numbers[0..j-1]该总和中是否存在数字的子集.

考虑对应于table[i][j](,这是真的)的子集S. 注意:

• numbers[j]仅当if table[ i-numbers[j] ][j-1]为true时 ,子集S才包含该数字.

  (证明:递归地获取解决方案子集S' table[ i-numbers[j] ][j-1],并添加numbers[j])

• 另一方面,numbers[j]仅当table[ i-numbers[j] ][j-1]false为false时,此子集S才包含该数字.

  (证明:假设S包含numbers[j],numbers[j]从S中删除,这意味着table[ i-numbers[j] ][j-1],矛盾)

因此,要获取子集,只需使用上面的属性来检查是否numbers[n-1]在子集中求和为t.

• 如果是这样,递归计算是否numbers[n-2]在子集中求和为t- numbers[n-1],
• 否则递归计算是否numbers[n-2]在子集中求和到t