使用动态编程找到子集和的解决方案
我想做的事
我想找到一个与目标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[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 ）是否存在numbers[0..j-1]中的numbers[0..j-1]子集，总和为i。
考虑对应于table[i][j]的子集S（其为真）。 注意：
- 仅当
table[ i-numbers[j] ][j-1]为真时，子集S才包含数字numbers[j]。
（certificate：递归地获取table[ i-numbers[j] ][j-1]的解集子S’，并添加numbers[j] ）
table[ i-numbers[j] ][j-1]为假时，该子集S不包含数字numbers[j] 。 （certificate：假设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;isum) 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 = sum-a[last_index] // then decrease the sum if(j>=a[i-1]) // ie 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][ja[i-1]]; // VERY VERY IMP NOTE: Here dp[i][j] on RHS 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 #include 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<