Java 使用动态规划找到子集和的解决方案

find a solution to subset sum using dynamic programming

提问by Arnab Datta

What I want to do

我想做的事

I want to find a subset of an array that sums to a target T. I also want to use to a dynamic programming approach (and a bottom-up solution at that) to do this.

我想找到总和为 target 的数组子集T。我还想使用动态编程方法（以及自下而上的解决方案）来做到这一点。

What I currently have

我目前拥有的

Currently I only found a way to see if amongst all subsets of size N, whether or not there is at least one subset that has the desired sum. See code below.

目前我只找到了一种方法来查看在 size 的所有子集中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];
}

Where I am stuck

我被卡住的地方

Right now, I know if there isa solution, but I can't think of a way to actually output a solution.

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

I am not looking for anyone to provide me specific code, but pseudocode is welcome as are hints to how a solution may be saved.

我不是在寻找任何人向我提供特定代码，但欢迎使用伪代码以及如何保存解决方案的提示。

采纳答案by user2831226

The algorithm you provided can stay the same, you don't need to store anything else besides the DP-table table[][]. You just need an additional post-processing phase in which you step "backwards" through table[][]to get the solution set.

您提供的算法可以保持不变，除了 DP-table 之外，您不需要存储任何其他内容table[][]。您只需要一个额外的后处理阶段，在该阶段您可以“向后”table[][]逐步获得解决方案集。

Just to recall:

只是回忆一下：

You've computed the table table[i][j], which stores for every value 0<=i<=t(:=target) and every 0<=j<=n(:=numbers.length) whether there is a subset of numbers in numbers[0..j-1]that sum to i.

您已经计算了 table table[i][j]，它为每个值 0<=i<=t(:= target) 和每个 0<=j<=n(:= numbers.length) 存储numbers[0..j-1]该总和中是否有数字的子集到 i。

Consider the subset S corresponding to table[i][j](, which is true). Note that:

考虑对应于table[i][j](，这是真的)的子集 S。注意：

• The subset S contains the number numbers[j]only if table[ i-numbers[j] ][j-1]is true.

  (Proof: recursively take the solution subset S' for table[ i-numbers[j] ][j-1], and add numbers[j])

• On the other hand, this subset S does not contain the number numbers[j]only if table[ i-numbers[j] ][j-1]is false.

  (Proof: assume S contains numbers[j], trow numbers[j]out of S, this implies table[ i-numbers[j] ][j-1], contradiction)

• 子集 Snumbers[j]仅在table[ i-numbers[j] ][j-1]为真时才包含数字。

  （证明：递归地取解子集 S' for table[ i-numbers[j] ][j-1]，并添加numbers[j]）

• 另一方面，该子集 Snumbers[j]仅当table[ i-numbers[j] ][j-1]为假时才包含数字。

  （证明：假设 S 包含numbers[j]，numbers[j]排除 S，这意味着table[ i-numbers[j] ][j-1]，矛盾）

所以要得到子集，只需使用上面的属性来检查是否numbers[n-1]numbers[n-1]在子集中求和到 t。

• If so, recursively compute whether numbers[n-2]is in the subset summing to t-numbers[n-1],
• else recursively compute whether numbers[n-2], is in the subset summing to t

• 如果是，递归计算是否numbers[n-2]在总和为 t- 的子集中numbers[n-1]，
• else 递归计算numbers[n-2], 是否在总和为 t 的子集中

回答by Kevin Bello

Here is my solution is an iterative dp, but with only one dimension: Hope it can help you.

这是我的解决方案是一个迭代 dp，但只有一个维度：希望它可以帮助你。

#include <iostream>
#include <cstring>

using namespace std;

const int maxN=1000;
int memo[maxN];
int pi[maxN];

int main(){
    int a[]={7,8,5,1,4};
    memset(memo,-1,sizeof memo);
    memset(pi,-1,sizeof pi);
    int n;
    cin>>n;
    memo[0]=0;
    pi[0]=0;
    for(int i=0;i<(int)sizeof(a)/4;i++){
        for(int num=n;num>=0;num--){
            if(num-a[i]>=0 and memo[num-a[i]]!=-1 and (memo[num]==-1 or memo[num]>1+memo[num-a[i]])){
                memo[num]=1+memo[num-a[i]]; 
                pi[num]=num-a[i];           
            }
        }
    }   
    int N=n;
    while(N!=0){
        cout<<N-pi[N]<<" ";
        N=pi[N];
    }
    cout<<endl;
    cout<<memo[n]<<endl;
    return 0;
}

回答by Nikhil Katre

Here are the two Java solutions for the subset sum problem.
First using Recursive Approach.
Second using Dynamic Programming Approach.

下面是子集和问题的两个 Java 解决方案。
首先使用递归方法。
其次使用动态规划方法。

/*
Question: Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set 
with sum equal to given sum.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.
Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with 
sum equal to sum. n is the number of elements in set[].


*/
package SubsetSumProblem;

import java.util.Scanner;

public class UsingResursiveAndDPApproach {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    try{
        System.out.println("Enter the number of elements in the array");
        int n =in.nextInt();
        System.out.println("Enter the elements of the array");
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=in.nextInt();
        System.out.println("Enter the sum, which you need to find");
        int sum = in.nextInt();
        System.out.println("Using recursion, the result is: "+usingRecursion(a,a.length,sum));
        System.out.println("Using Dynamic Programming, the result is: "+usingDP(a,sum));
    }
    finally{
        in.close();
    }
}


private static boolean usingRecursion(int[] a,int length, int sum) {

    // 1. Base Cases
    if(sum==0)
        return true;
    if(length==0 && sum!=0)
        return false;

    // 2. To avoid unnecessary steps, we will optimize the recursion method by avoiding 
    //    recursive calls to areas where we are definite that we can SAFELY ignore the case since
    //    the SOLUTION does not exist there.

    // If last element is greater than sum, then ignore it
    if(a[a.length-1]>sum)
        return usingRecursion(a,length-1,sum);

    // 3. This is the recursion step where we will call the method again and again
    /* else, check if sum can be obtained by any of the following
    (a) including the last element
    (b) excluding the last element   */
    return (usingRecursion(a, length-1, sum-a[length-1])|| usingRecursion(a, length-1, sum));

}
/*
Analysis:
    Time Complexity = O(2^n)
    Space Complexity =       // Don't know
*/

private static boolean usingDP(int[] a, int sum) {
    // using boolean matrix for DP
    boolean dp[][] = new boolean[a.length+1][sum+1];  // +1 in row and column


    // if the length of the array is variable (and sum is 0) then fill TRUE, since the SUM=0 
    for(int row=0;row<dp.length;row++){
        dp[row][0] = true;    // NOTE: dp[length=VARIABLE][sum=0], thus we satisfy the condition where length is VARIABLE
                              // and the SUM=0
    }

    // if the SUM is variable and length is 0 then FALSE, since (sum=variable && length=0)
    for(int column=1;column<dp[0].length;column++){
        dp[0][column] = false;  // NOTE: dp[length=0][sum=VARIABLE], thus we satisfy the condition where 
                                // (length=0 && sum=variable)
    }

    for(int i=1;i<dp.length;i++){
        for(int j=1;j<dp[0].length;j++){


            /* Check if sum can be obtained by any of the following
              (a) including the last element
              (b) excluding the last element   */


            // VERY VERY IMP: This is same as "excluding the last element" which is represented in DP 
            dp[i][j] = dp[i-1][j]; // the current position[i][j] would be same as previous position.
                                   // the previous position means that SUM is ACHIEVED OR NOT-ACHIEVED
                                   // int the previous position then it will ofcourse be ACHIEVED or NOT-ACHIEVED
                                   // in the current position.


            // VERY VERY IMP: This is same as "including the last element" which is represented in DP 
            // if the column[ sum is represented in column of the matrix i.e this sum exist] > = sum-a[last_index]
            // then decrease the sum
            if(j>=a[i-1])   // i.e sum >= array[last index element]. If it is true then include this last element by
                            // deducting it from the total sum
                dp[i][j] = dp[i][j] || dp[i-1][j-a[i-1]];  // VERY VERY IMP NOTE: Here dp[i][j] on R.H.S represent
                            // dp[i-1][j] which we have assigned in the previous step

        }
    }
    return dp[a.length][sum];
}
/*
Analysis:
    Time Complexity = O(a.length*sum)
    Space Complexity = O(a.length*sum)
*/
}