代码随想录-背包问题
01背包
问题 ： 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
二维数组解法
动规五部曲 ：
确定dp数组以及下标的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
确定递推公式
dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);
dp数组如何初始化
1
2
3
4
5
6
7for (int j = 0 ; j < weight[0]; j++) {
dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}确定遍历顺序 （两种）
上面是对于dp[i] [j]的一个图。可以看到，i是代表从下标为0~i的物品里随便取，j是背包重量。那么可以先遍历i或者先遍历j
先物品再背包
理解 ： 这就是先遍历i 。具体可以解释为 ：先给定物品的选择范围（0~i），在这个范围里面，看各个背包重量下j，能取到的价值最大值。
递推就是 ： 拿i个物品的最大值，需要用拿i-1个物品的最大值来递推。
1
2
3
4
5
6
7
8// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}先背包再物品
理解 ： 这就是先遍历j 。具体可以解释为 ： 先给定背包的重量j ，求在这个背包重量下，如何在所有物品中找到一个组合，能够得到价值最大值。
递推也是 ： 拿i个物品的最大值，需要用拿i-1个物品的最大值来递推。
1
2
3
4
5
6
7// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
for(int i = 1; i < weight.size(); i++) { // 遍历物品
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
举例推导dp数组
完整代码
动态规划的核心思想避免重复计算在01背包问题中体现得淋漓尽致。
第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定
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
59public class BagProblem {
public static void main(String[] args) {
int[] weight = {1,3,4};
int[] value = {15,20,30};
int bagSize = 4;
testWeightBagProblem(weight,value,bagSize);
}
/**
* 动态规划获得结果
* @param weight 物品的重量
* @param value 物品的价值
* @param bagSize 背包的容量
*/
public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
// 创建dp数组
int goods = weight.length; // 获取物品的数量
int[][] dp = new int[goods][bagSize + 1];
// 初始化dp数组
// 创建数组后，其中默认的值就是0
for (int j = weight[0]; j <= bagSize; j++) {
dp[0][j] = value[0];
}
// 填充dp数组，这里是先物品再背包
for (int i = 1; i < weight.length; i++) {
for (int j = 1; j <= bagSize; j++) {
if (j < weight[i]) {
/**
* 当前背包的容量都没有当前物品i大的时候，是不放物品i的
* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
*/
dp[i][j] = dp[i-1][j];
} else {
/**
* 当前背包的容量可以放下物品i
* 那么此时分两种情况：
* 1、不放物品i
* 2、放物品i
* 比较这两种情况下，哪种背包中物品的最大价值最大
*/
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]); //也就是递推公式
}
}
}
// 打印dp数组
for (int i = 0; i < goods; i++) {
for (int j = 0; j <= bagSize; j++) {
System.out.print(dp[i][j] + "\t");
}
System.out.println("\n");
}
}
}
一维数组解法
首先来回味一下二维数组的递推公式 ：
dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了（i没有存在的必要了） :
dp[j]
这个dp[j]就是一个滚动数组（需要满足的条件是上一层可以重复利用，直接拷贝到当前层。）
如此一来 ，动规五部曲可以写成 ：
确定dp数组含义
dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
dp数组的递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);解释:
dp[j]可以通过dp[j - weight[i]]推导出来（这一点参考上面的二维数组dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]);）dp[j - weight[i]] ： 容量为j - weight[i]的背包所背的最大价值。dp[j - weight[i]] + value[i] : 容量为(j - 物品i重量)的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）公式中的 dp[j] ： 二维dp数组中的dp[i-1][j]，即不放物品i公式中的dp[j - weight[i]] + value[i] ： 即放物品idp数组的初始化
dp数组初始化的时候，都初始为0就可以了。
dp数组遍历
1
2
3
4
5
6
7
8for(int i = 0; i < weight.size(); i++) { // 遍历物品
// 遍历背包容量 ： 从大到小 ！
// 如果从小到大，就是完全背包 ！
for(int j = bagWeight; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}解释：
由二维数组下状态转移方程可知，
dp[i][j]的值只与dp[i-1][0,...,j-1]有关，所以我们可以采用动态规划常用的方法（滚动数组）对空间进行优化（即去掉dp的第一维）。需要注意的是，为了防止上一层循环的
dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举（空间优化前没有这个限制）代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWight = 4;
testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
完全背包
直接滚动数组来写。
与01背包的不同点在于，对于物品的拿出没有限制。
背包小总结
递推公式
背包的最大值 ：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
达到背包最大值的方法数（排列还是组合在遍历时有区别）：
dp[j] += dp[j - nums[i]]
达到背包最大值的最小物品数量：
dp[j] = min(dp[j]，dp[j - weight[i]] + value[i]);
遍历顺序
01背包求组合/最大值
外层for循环遍历物品，内层for遍历背包（物品从0下标开始，背包从bagWeight开始，– 至weight[i]）
完全背包求最大值
外层for循环遍历物品，内层for遍历背包（物品从0下标开始，背包从nums[i]下标开始 ， ++ 至 bagWeight）
完全背包求方法数
求组合数 ： 外层for循环遍历物品，内层for遍历背包。（物品从0下标开始，背包从nums[i]下标开始）
求排列数 ： 外层for循环遍历背包，内层for循环遍历物品。（背包和物品都从0下标开始）
416.分割等和子集（01求max）
一维写法
1 | /** |
二维写法
1 | /** |
1049.最后一块石头的重量Ⅱ（01求max）
分成两堆转化成背包问题，要思考清楚最后到底剩多少
1 | /** |
494.目标和（01求组合）
这里不是求能不能装满背包，
而是求能装满背包的方法。
另外要充分考虑特殊情况。
1 | /** |
474.一和零(01求组合、二维物品)
物品是二维的，。思想是一维（滚动数组）的。
1 | /** |
518.零钱兑换Ⅱ（完全求组合）
完全背包的基本应用
1 | /** |
377.组合总和Ⅳ（完全求排列）
1 | /** |
322.零钱兑换（完全求最小物品数）
难点 ： 在于初始化
1 | /** |
279.完全平方数（完全求最小物品数）
类似322.零钱兑换
1 | /** |
139.单词拆分（字符串的背包形式）
1 | /** |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 罗辑往事！
