子集和问题是我在麦卡莱斯特学到的第一个NP完全问题。这个问题已经被查看了36000多次,但我没有看到一个足够详细解释算法逻辑的答案。因此,我想尝试做到这一点。
假设:
为了简单起见,我首先假设输入集合X
仅包含正整数,k
为正数。然而,我们可以调整算法以处理负整数和k
为负数的情况。
逻辑:
这个算法或者说任何DP问题的关键是将问题分解并从基本情况开始简单地开始。然后,我们可以使用我们所知道的一些知识来构建基本情况:
- 我们知道如果集合
X
为空,则无法将任何值的k
相加。
- 如果集合
X
包含k
,则它有一个子集相加为k
。
- 我们知道如果集合
x1
的子集之一是X
的子集且和为k1
,则X
将有一个子集和为k1
,即x1
。
- 我们有一个集合
X = {x1, x1, x3, ......., xn, xn+1}
。如果x1 = {x1, x1, x3, ......., xn}
中有一个子集的和为k-k1
,则我们知道它有一个子集和为k1
。
示例以说明1,2,3,4:
- 如果你有一个空集 {},那么你就没有子集,因此你也没有任何子集和。
一个集合 X = {4}
有一个子集和为 4,因为 4 本身就是该集合的一部分
假设你有一个集合 x1 = {1,3,5}
是集合 X = {1,3,5,2,8}
的子集。如果 x1
有一个子集和为 k1 = 8
,那么这意味着 X
也有一个子集和为 8,因为 x1
是 X
的子集
- 假设你有一个集合
X = {1,3,5,2,19}
,我们想知道它是否有一个子集和为 20。它有,并且可以通过以下方式确定: x1 = {1,3,5,2}
可以求和 (20 - 19) = 1。由于 x1 有一个子集和为 1,因此当我们将 19 添加到集合 x1 中时,我们可以取得新数字 1 + 19 = 20 来创建我们所需的总和 20。
动态构建矩阵
太棒了!现在让我们利用上述四个逻辑从基本情况开始构建。我们将构建一个矩阵 m
。我们定义:
(请注意,维基百科的答案或大多数人都会构建一个函数m(i,s)
,但我认为矩阵是理解动态编程的简单方法。当我们在集合或数组中只有正数时,它很有效。然而,函数路线更好,因为你不必处理索引超出范围,匹配数组的索引和总和到矩阵.....)
让我们用一个例子来构建矩阵:
X = {1,3,5,2,8}
k = 9
我们将逐行构建矩阵。最终,我们想知道单元格m[n][k]是否包含true或false。
第一行:
逻辑1告诉我们,矩阵的第一行应全部为false。
0 1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1|
2|
3|
4|
5|
第二行及以上:
然后对于第二行或以上,我们可以使用2、3、4逻辑来帮助我们填充矩阵。
- 逻辑2告诉我们
m[i][s] = (X[i-1] == s)
记住m[i]是指X中的第i个项目,即X[i-1]
- 逻辑3告诉我们
m[i][s] = (m[i-1][s])
这是查看直接上方的单元格。
- 逻辑4告诉我们
m[i][s] = (m[i-1][s - X[i-1]])
这是查看X[i-1]单元格上方和左侧的行。
如果任何一个逻辑为true
,那么m[i][s]
就是true
,否则就是false
。因此,我们可以将2、3、4重写为m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])
使用以上逻辑填充矩阵m
。在我们的示例中,它看起来像这样。
0 1 2 3 4 5 6 7 8 9
_ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F
3| F T F T T T T F T T
4| F T T T T T T T T T
5| F T T T T T T T T T
现在使用矩阵来回答你的问题:
看一下原始问题m[5][9]
。使用前5个项目(即所有项目),我们可以找到一个子集和为9(k)吗?答案由该单元格指示,即true
以下是代码:
import java.util.*;
public class SubSetSum {
public static boolean subSetSum(int[] a, int k){
if(a == null){
return false;
}
int n = a.length;
boolean[][] m = new boolean[n + 1][k + 1];
for(int s = 0; s <= k; s++){
m[0][s] = false;
}
for(int i = 1; i <= n; i++){
for(int s = 0; s <= k; s++){
if(s - a[i-1] >= 0){
m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]);
} else {
m[i][s] = (m[i-1][s] || a[i-1] == s);
}
}
}
print(m);
return m[n][k];
}
private static void print(boolean[][] m){
for(int i = 0; i < m.length; i++){
for(int j = 0; j < m[i].length; j++){
if(m[i][j]){
System.out.print("T");
} else {
System.out.print("F");
}
}
System.out.print("\n");
}
}
public static void main(String[] args){
int[] array = {1,3,5,2,8};
int k = 9;
System.out.println(subSetSum(array,k));
}
}
构建矩阵的复杂度为O((n+1)(k+1)),即O(nk)。看起来应该是多项式的,但实际上它是伪多项式的。在
这里了解更多信息。
再次说明,这仅适用于输入只包含正数的情况。您可以轻松地将其调整为使用负数的情况。矩阵仍将具有n+1行,但是
B-A+1
列。其中
B
是上限,
A
是下限(+1包括零)。矩阵仍将是的。您必须使用下限偏移
s
。
通过文本从头到尾解释DP问题非常困难。但我希望这对那些试图理解此问题的人有所帮助。
请注意,在上面的示例中,DP表的行已排序。这不一定是必要的。
这是一个DP表,用于问题的情况,即给定{5、3、11、8、2}的集合。为简洁起见,我省略了错误值。
┌─────────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ (index) │ 0 │ 2 │ 3 │ 5 │ 7 │ 8 │ 10 │ 11 │ 13 │ 14 │ 15 │ 16 │
├─────────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ 0 │ true │ │ │ │ │ │ │ │ │ │ │ │
│ 5 │ true │ │ │ true │ │ │ │ │ │ │ │ │
│ 3 │ true │ │ true │ true │ │ true │ │ │ │ │ │ │
│ 11 │ true │ │ true │ true │ │ true │ │ true │ │ true │ │ true │
│ 8 │ true │ │ true │ true │ │ true │ │ true │ true │ true │ │ true │
│ 2 │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │
└─────────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘
以下是JavaScript中的实现,将输出目标集{5, 11}:
var subSetSum = function(input, sum) {
let y = input.length;
let x = sum;
if(input.length === 0) return 0;
let d = [];
for (let i = 0; i <= y; i++) {
d[i] = [];
d[i][0] = true;
}
for (let j = 1; j <= y; j++) {
for (let i = 1; i <= x; i++) {
let num = input[j-1];
if(num === i) {
d[j][i] = true;
} else if(d[j-1][i]) {
d[j][i] = true;
} else if (d[j-1][i-num]) {
d[j][i] = true;
}
}
}
if(!d[y][x]) return null;
let searchedSet = [];
for(let j=input.length, i=sum; j>0 && i != 0; j--) {
if(input[j-1] !== i) {
while(d[j-1][i]) {
j--;
}
}
searchedSet.push(input[j-1]);
i = i-input[j-1];
}
return searchedSet;
};
console.log('searched set:'+ JSON.stringify(subSetSum([5, 3, 11, 8, 2], 16)));