0-1背包问题
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
实例1：
背包最大重量为4
物品为：
|
重量 |
价值 |
| 物品0 |
1 |
15 |
| 物品1 |
3 |
20 |
| 物品2 |
4 |
30 |
解题思路
动态规划
1.确定dp数组及下标的含义
dp[j]表示：容量为 j 的背包，所背的物品价值可以最大为dp[j]
2.确定递推公式
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] + value[i] 表示容量为 j - weight[i] 的背包加上物品 i 的价值。
dp[j] 有两个选择，一个是不放物品i ，即dp[i] 本身，一个是放物品 i ，为dp[j - weight[i]] + value[i]
故递推公式为
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
3.初始化dp数组
dp[0] = 0表示背包容量为0时的最大价值为0
而又由递推公式dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0即可
4.确定遍历顺序
滚动数组，先遍历物品，再遍历背包容量，因为下一个物品放入背包的状态要由上一个物品放入背包的状态推出来
1
2
3
4
5
6
| for(int i = 0 ; i < item_num; i++){
for(int j = bagweight; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
|
倒序遍历是为了保证物品i只被放入一次，一旦正序遍历了，那么物品0就会被重复加入多次
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了
dp数组的状态如图
代码
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
| public class bagProblem {
public static void main(String[] args){
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagweight =4;
weightbagproblem02(weight, value, bagweight);
}
public static void bagproblem02(int[] weight, int[] value, int bagweight){
int item_num = weight.length;
int[] dp = new int[bagweight+1];
for(int i = 0 ; i < item_num; i++){
for(int j = bagweight; j>=weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
System.out.println("01背包问题的答案为：" + dp[bagweight]);
}
public static void bagProblem(int[] weight, int[] value, int bagweight){
int item_num = weight.length;
int[][] dp = new int[item_num][bagweight+1];
for(int i = 0 ; i < item_num; i++){
dp[0][i] = 0;
}
for(int j = 0; j < weight[0]; j++){
dp[0][j] = 0;
}
for(int j = weight[0]; j<=bagweight; j++){
dp[0][j] = value[0];
}
for(int i = 1; i < item_num; i++){
for(int j = 1; j <= bagweight; j++){
if(j<weight[i]){
dp[i][j] = dp[i-1][j];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
}
}
}
System.out.println("01背包问题的答案为：" +dp[item_num-1][bagweight]);
}
}
|
- 时间复杂度：$O(m × n)$ , m背包容量，n为物品的数量
- 空间复杂度：$O(m)$，采用滚动数组可以压缩空间复杂度