我想做什么
我想找到一个数组的子集，该数组的总和为目标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];
}
我被困在哪里
现在，我知道是否有解决方案，但我想不出实际输出解决方案的方法。
我不是在寻找任何人为我提供特定的代码，但欢迎伪代码以及如何保存解决方案的提示。
您提供的算法可以保持不变，除了DP表table[][]之外，您不需要存储任何其他内容。您只需要一个额外的后处理阶段，在该阶段中，您可以"向后"table[][]步骤以获得解决方案集。
只是为了回想一下：
您已经计算了表 table[i][j] ，它存储每个值 0<=i<=t（：= target ） 和每个 0<=j<=n（：= numbers.length ） 中是否存在总和为 i 的数字numbers[0..j-1]子集。
考虑对应于 table[i][j] 的子集 S（，这是真的）。请注意：
- 子集 S 仅当
table[ i-numbers[j] ][j-1]为 true 时才包含数字numbers[j]。（证明：递归取解子集S'作为
table[ i-numbers[j] ][j-1]，并加numbers[j]） - 另一方面，此子集 S 不包含数字
numbers[j]仅当table[ i-numbers[j] ][j-1]为 false 时才。（证明：假设S包含
numbers[j]，从S中numbers[j]出，这意味着table[ i-numbers[j] ][j-1]，矛盾）
numbers[n-1]是否在总和为 t 的子集中。- 如果是这样，递归计算
numbers[n-2]是否在总和为 t-numbers[n-1]的子集中， - 否则递归计算
numbers[n-2]是否在总和为 t 的子集中
以下是子集和问题的两种 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)
*/
}
这是我的解决方案是一个迭代的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;
}