背包问题
小偷有一个承重为W的背包，有n件物品，第i个物品价值vi，且中wi
目标：在背包称重允许的情况下，抢到尽可能价值高的物品
- 利用暴力回溯法求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class Test3 {
int n = 100;
int[] v = new int[n];
int[] w = new int[n];
int W = 50;
int rob(int idx,int S){
if(idx >= n || S > W){
return 0;
}
return Math.max(rob(idx + 1 , S + v[idx]),
rob(idx + 1 , S));
}
}
|
分析该种算法的时间复杂度为O(2^n)
- 利用存储方式存放以及计算过的值
暴力法的O(2^n)的时间复杂度是很高的，当n稍微大一点的时候需要的时间呈指级增长 ，因此可以利用空间换时间的方法，降低时间复杂度 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Test3 {
int n = 100;
int[] v = new int[n];
int[] w = new int[n];
int W = 50;
int[][] result = new int[n][];
int rob(int idx,int S){
if(idx >= n || S > W){
return 0;
}
if(result[idx][S]>0){
return result[idx][S];
}
result[idx][S] = Math.max(result[idx + 1][S + v[idx]],
result[idx + 1][S]);
return result[idx][S];
}
}
|
那么再来分析一下时空复杂度，空间复杂度毫无疑问就是新开辟的result数组，它的每一行表示的时第idx个物品，每一列表示到当前物品时身上的物品的重量，因此空间复杂度为O(nW) ,而时间复杂度怎么计算？在这个程序中，真正运算过一遍的值也就是result数组中的值，所以时间复杂度也是O(nW)，这样就是利用空间换取时间。
然而，递归的写法还是不能计算太大的值，在java中，当递归的层数多的时候会抛栈溢出异常，最好把这个程序改写成递推的方式 。
- 利用递推写法防止栈溢出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public class Test3 {
int n = 100;
int[] v = new int[n];
int[] w = new int[n];
int W = 50;
int[][] result = new int[n+1][];
int rob(int idx,int S){
result[0][0] = 0;
for (int i=1;i<=W;i++){
result[0][i] = Integer.MIN_VALUE;
}
for(int i=1;i<=n;i++){
result[i][0] = 0;
for(int j=1;j<=W;j++){
result[i][j] = result[i - 1][j];
if(j >= w[i]){
result[i][j] = Math.max(result[i - 1][j + w[i]],
result[i][j]);
}
}
}
return result[idx][S];
}
}
|
我们发现，第i行的值只与i-1行有关，就是计算第i行，只需要知道i-1行即可，那么就是说只需要2行的数组就可以满足需求
- 能不能再减少空间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public class Test3 {
int n = 100;
int[] v = new int[n];
int[] w = new int[n];
int W = 50;
int[][] result = new int[n+1][];
int rob(int idx,int S){
result[0][0] = 0;
for (int i=1;i<=W;i++){
result[0][i] = Integer.MIN_VALUE;
}
for(int i=1;i<=n;i++){
int a = i % 2;
int b = (i - 1) % 2;
result[a][0] = 0;
for(int j=1;j<=W;j++){
result[a][j] = result[b][j];
if(j >= w[i]){
result[a][j] = Math.max(result[b][j + w[i]],
result[a][j]);
}
}
}
return result[idx][S];
}
}
|
