动态规划初级版0-1背包
题目来源于acwing
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
注意本篇文章可能非常长，后面还介绍了恰好装满背包的情况
先上初级代码
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| import java.util.*;
public class Main {
public static int solve (int[] v,int[] w,int N,int V){
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= v[i])
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
show(dp);
}
int ans = 0;
for (int i = 0;i <= V; i++) {
ans = Math.max(ans, dp[N][i]);
}
return ans;
}
public static void show(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j <arr[i].length; j++) {
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
System.out.println("*");
}
public static void main (String[] args) {
Scanner sc=new Scanner (System.in);
int N,V;
N = sc.nextInt();
V = sc.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(solve(v,w,N,V));
}
}
|
可以看出每次我们只需要用到i-1层的数据，在网上的都没用，所以可以更进一步压缩空间。
二维变一维：数组的含义没变，j需要从大到小遍历。
从小到大遍历的话，dp[i - 1][j - v[i]] + w[i]，这个式子会变成->dp[j-v[i]]+w[i]，每次相加的时候用到的是第i次的值，而不是i-1次的值，也就是说这么遍历会把i-1次的值覆盖住。而从大往小遍历，由于我们用到的是j-v[i]这个体积，从大往小的话这个值一定比当前的体积小，所以不会发生更新被覆盖的情况。
更改如下 ↓↓↓
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 static int solve (int[] v,int[] w,int N,int V){
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
for (int j = V; j >= 0; j--) {
if(j >= v[i])
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
show(dp);
}
return dp[V];
}
|
更改条件
如果是恰好能够装满并且价值最大，在初始化上做手脚，f[0]=0其余全部为-INF。其实只需要赋值为一个正常情况下不能到达的值就行。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| public static int solve (int[] v,int[] w,int N,int V){
int[] dp = new int[V + 1];
int inf = Integer.MIN_VALUE;
for (int i = 1; i <= V; i++)
dp[i] = inf;
for (int i = 1; i <= N; i++) {
for (int j = V; j >= 0; j--) {
if(j >= v[i]) {
System.out.println("j= "+j+" j-v[i]= "+(j- v[i])+" dp[j-v[i]]= "+ dp[j-v[i]]);
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
show(dp);
}
return dp[V] >= 0 ? dp[v] : -1;
}
|
这样就很清晰，因为要恰好放j重量，所以每一次也必须保证最大重量为j，在不修改dp数组的情况下可以增加一个max阈值。（因为我觉得一般人应该不会能直接想到用负无穷吧）
第二天我发现这个没办法判断不能组成时候的情况，所以仅给出一个思路吧。
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
32
33
34
35
36
37
38
39
40
41
42
| public static int solve (int[] v,int[] w,int N,int V){
int[] dp = new int[V + 1];
int max = 0;
for (int i = 1; i <= N; i++) {
max+= v[i];
if (max > V) max = V;
for (int j = max; j >= 0; j--) {
if(j >= v[i]) {
System.out.println("j= "+j+" j-v[i]= "+(j- v[i])+" dp[j-v[i]]= "+ dp[j-v[i]]);
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
show(dp);
}
int ans = 0;
return dp[V];
}
|
先总结到这，已经3500字了，背包的下一个版本在下一篇文章中见。