给定一个整数数组和一个总和,任务是打印给定数组的所有子集,总和等于给定总和。
Example:
Input : arr[] = {1, 2, 3, 4, 5}
sum = 10
Output : [4 3 2 1]
[5 3 2]
[5 4 1]
Input : arr[] = {-1, 2, 3, 4, 5}
sum = 10
Output : [5 3 2]
[5 4 2 -1]
我已经在伪多项式时间内使用动态规划完成了这项工作。这是子集和问题的扩展,它只负责判断这样的子集是否存在。我下面的解决方案适用于子集和问题的正数和负数。但是,如果数组包含负数,则无法正确打印子集。程序是-
import java.util.ArrayList;
// sum problem
class GFG {
static boolean subset[][];
// Returns true if there is a subset of
// set[] with sun equal to given sum
static boolean isSubsetSum(int set[],
int n, int sum) {
// The value of subset[i][j] will be
// true if there is a subset of
// set[0..j-1] with sum equal to i
subset = new boolean[n + 1][sum + 1];
// Fill the subset table in botton
// up manner
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
if (j == 0) {
subset[i][j] = true;
} else if (i <= 0 && sum >= 1)
subset[i][j] = false;
else if (set[i - 1] > j)
subset[i][j] = subset[i - 1][j];
else {
if (set[i - 1] >= 0)
subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
else
subset[i][j] = subset[i - 1][j] || subset[i - 1][j + set[i - 1]];
}
}
}
// uncomment this code to print table
// for (int i = 0; i <= sum; i++)
// {
// for (int j = 0; j <= n; j++)
// System.out.println (subset[i][j]);
// }
return subset[n][sum];
}
/* Driver program to test above function */
public static void main(String args[]) {
int set[] = {1, 2, 3, 4, 5};
int sum = 10;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset"
+ " with given sum");
else
System.out.println("No subset with"
+ " given sum");
System.out.println("Done");
ArrayList<Integer> list = new ArrayList<>();
printSubsets(set, n, sum, list);
System.out.println("Finished");
}
static void display(ArrayList<Integer> v) {
System.out.println(v);
}
private static void printSubsets(int[] set, int i, int sum, ArrayList<Integer> list) {
if (i == 0 && sum != 0 && subset[0][sum]) {
list.add(set[i]);
display(list);
list.clear();
return;
}
// If sum becomes 0
if (i == 0 && sum == 0) {
display(list);
list.clear();
return;
}
// If given sum can be achieved after ignoring
// current element.
if (subset[i - 1][sum]) {
// Create a new vector to store path
ArrayList<Integer> b = new ArrayList<>();
b.addAll(list);
printSubsets(set, i - 1, sum, b);
}
// If given sum can be achieved after considering
// current element.
if (sum >= set[i - 1] && subset[i - 1][sum - set[i - 1]]) {
list.add(set[i - 1]);
printSubsets(set, i - 1, sum - set[i - 1], list);
}
}
}
如何修改此代码以使其也适用于负数?
最佳答案
您的解决方案假设所有值都是正数,因此动态编程数组 subset
填充了 j
的正值,但您需要考虑现在是负和。
你需要做的是改变j
的循环限制来填充动态规划数组为
for (int j = negative_sum; j <= positive_sum; j++)
其中 negative_sum
是所有负值的总和,positive_sum
是所有正值的总和。
有关更多详细信息,请阅读子集和问题的维基百科页面 here解释这一步的地方。
关于java - 动态规划 : perfect sum with negative numbers,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52399530/