因此,基本上它与子集求和问题的想法相同,但有一个限制:找到的子集需要具有偶数大小。
例如:
numbers {4, 3, 3, 5, 1, 2, 7, 12}
find subset that sums up to 10
=> solution: {4, 3, 1, 2} (or {3, 7} but not {4, 3, 3} )
有没有一种简单的方法可以找到这样的子集? (该方法应该是“高效的”,而不是只是尝试所有可能的子集...)
这是我找到“正常”子集的代码:
int n = 8;
int m = 11;
boolean[][] S = new boolean[n][m];
int[] N = new int[] {4, 3, 3, 5, 1, 2, 7, 12};
S[0][0] = true;
S[0][S[0]] = true;
for(int i = 1; i < n; i++) {
for(int j = 0; j < m; j++) {
if(N[i] == j) {
S[i][j] = true;
} else if(j - N[i] >= 0) {
S[i][j] = S[i-1][j] || S[i-1][j - N[i]];
} else {
S[i][j] = S[i-1][j];
}
}
}
最佳答案
在您当前的代码中,如果您可以将值 j 作为不超过 i 的数字的子集,则 S[i][j] 为真。
相反,如果您可以将值 j 作为最多 i 个数字的子集,并且使用的数字数量等于 k 模 2,则计算 S[i][j][k] 为真。
换句话说,k 要么是 0,要么是 1。
这将需要大约两倍于现有解决方案的计算。
关于java - 子集总和但偶数子集大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47595716/