给定一组非负整数和一个值总和,确定给定集合中是否存在总和等于给定总和的子集。
例如:
set = {1,2,5,7}
sum = 8
=> true
我实际上用这段代码解决了问题:
public boolean isSubsetSum(int[] set, int sum) {
Arrays.sort(set);
boolean[][] memo = new boolean[set.length+1][sum+1];
for (int i = 0; i < memo.length; i++) {
memo[i][0] = true;
}
for (int i = 1; i < memo.length; i++) {
for (int j = 1; j < memo[i].length; j++) {
if (set[i-1] > j) {
memo[i][j] = memo[i-1][j];
} else {
memo[i][j] = memo[i-1][j] || memo[i-1][j-set[i-1]];
}
}
}
return memo[memo.length-1][memo[memo.length-1].length-1];
}
但是,现在我想重构构成给定总和的所有可能组合。
是否可以从我的内存矩阵中做到这一点,还是我必须以不同的方式来做到这一点?
最佳答案
创建一个名为 take[i][j]
的新 DP 表,它是 boolean 值。如果您将 i-th
元素用于子集总和 j
,则为真。你用你的普通备忘录表同时填充它:
for (int i = 1; i < memo.length; i++) {
for (int j = 1; j < memo[i].length; j++) {
if (memo[i-1][j]){
//no need to take ith elements, first i-1 have sum j
take[i][j] = false;
memo[i][j] = true;
}
else if (j-set[i-1] >= 0 && memo[i-1][j-set[i-1]]){
//take ith element, and search for set of size j-set[i-1] in 1..i-1
take[i][j] = true;
memo[i][j] = true;
}
else{
//neither memo[i-1][j] or memo[i-1][j-set[i-1]] valid, so no way to make sum
take[i][j]=false;
memo[i][j]=false;
}
}
}
最后,要重构解决方案,您可以从:
开始int i =set.length
int j = sum
while (i>=0 && j>=0){
if (take[i][j]){
print(set[i])
j = j - set[i]
i=i-1
}
else{
i=i-1
}
}
您可以将此概括为所有解决方案集。
关于java - 动态规划 - 子集和 - 重建路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47620309/