对于面试的话,其实掌握01背包,和完全背包,就够用了,最多可以再来一个多重背包。
如果这几种背包,分不清,就看下图
leetcode上连多重背包的题目都没有,这就告诉我们,01背包和完全背包就够用了。
而完全背包又是01背包稍作变化而来,即:完全背包的物品数量是无限的。
所以背包问题的理论基础重中之重是01背包,一定要理解透!
leetcode上没有纯01背包的问题,都是01背包应用方面的题目,也就是需要转化为01背包问题。
所以后面先通过纯01背包问题,把01背包原理理解清楚,后续再写eetcode题目的时候,重点就是讲解如何转化为01背包问题了。
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大
这是标准的背包问题,以至于很多同学看了这个自然就会想到背包,甚至都不知道暴力的解法应该怎么解了。
这样其实是没有从底向上去思考,而是习惯性想到了背包,那么暴力的解法应该是怎么样的呢?
每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是 o ( 2 n ) o(2^n) o(2n),这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化!
在下面的讲解中,我举一个例子:
背包最大重量为4。
物品为:
重量 | 价值 | |
---|---|---|
物品0 | 1 | 15 |
物品1 | 3 | 20 |
物品2 | 4 | 30 |
问背包能背的物品最大价值是多少?
以下讲解和图示中出现的数字都是以这个例子为例。
确定dp数组含义:编号为0-i的物品,任取放入容量为j的背包,最大价值为dp[i][j]
对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
要时刻记着这个dp数组的含义,下面的一些步骤都围绕这dp数组的含义进行的,如果哪里看懵了,就来回顾一下i代表什么,j又代表什么。
确定递归公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[j])
再回顾一下dp[i][j]的含义:从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。那么可以有两个方向推出来dp[i][j],
不放物品i,最大价值为:dp[i - 1][j]
放物品i:dp[i - 1][j - weight[i]] + value[j]
dp数组初始化:dp[0][j] dp[i][0]
关于初始化,一定要和dp数组的定义吻合,否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发,如果背包容量j为0的话,即dp[i][0],无论是选取哪些物品,背包价值总和一定为0。
在看其他情况。
状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来,那么i为0的时候就一定要初始化。
dp[0][j],即:i为0,存放编号0的物品的时候,各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候,dp[0][j] 应该是 0,因为背包容量比编号0的物品重量还小。
当j >= weight[0]时,dp[0][j] 应该是value[0],因为背包容量放足够放编号0物品。
物品i\容量j | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
0 | 0 | value[0](如果能放的话) | value[0](如果能放的话) | value[0](如果能放的话) | value[0](如果能放的话) |
1 | 0 | max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[j]) | |||
2 | 0 | ||||
3 | 0 | ||||
4 | 0 |
dp[0][j] 和 dp[i][0] 都已经初始化了,那么其他下标应该初始化多少呢?
其实从递归公式: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出dp[i][j] 是由左上方数值推导出来了,那么 其他下标初始为什么数值都可以,因为都会被覆盖。
初始-1,初始-2,初始100,都可以!
但只不过一开始就统一把dp数组统一初始为0,更方便一些。
遍历顺序:二维数组的话,先遍历背包或先遍历物品都可以
dp[i][j] = max(dp[i - 1]\j], dp[i - 1][j - weight[i]] + value[i]); 递归公式中可以看出dp[i][j]是靠dp[i-1][j]和dp[i - 1][j - weight[i]]推导出来的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正上方向)
debug:打印dp数组
第一行包含两个正整数,第一个整数 M 代表研究材料的种类,第二个正整数 N,代表小明的行李空间。
第二行包含 M 个正整数,代表每种研究材料的所占空间。
第三行包含 M 个正整数,代表每种研究材料的价值。
输出一个整数,代表小明能够携带的研究材料的最大价值。
6 1
2 2 3 1 5 2
2 3 1 5 4 3
5
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String... args) {
Scanner scanner = new Scanner(System.in);
int M;
int bagSize;
M = scanner.nextInt();
bagSize = scanner.nextInt();
// System.out.println("M:" + M +" bagSize:" + bagSize);
int[] weight = new int[M];
int[] value = new int[M];
for(int i = 0; i < M; i++) {
weight[i] = scanner.nextInt();
}
// System.out.println("weight数组:" + Arrays.toString(weight));
for(int i = 0; i < M; i++) {
value[i] = scanner.nextInt();
}
// System.out.println("value数组:" + Arrays.toString(value));
int res = testWeightBagProblem(weight, value, bagSize);
System.out.println(res);
}
public static int testWeightBagProblem(int[] weight, int[] value, int bagSize) {
int[][] dp = new int[weight.length][bagSize + 1];
//初始化dp数组,第一列默认值就是0
for(int j = weight[0]; j <= bagSize; j++) {
dp[0][j] = value[0];
}
for(int i = 1; i < weight.length; i++) {
for(int j = 1; j <= bagSize; 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]));
}
}
}
// testAndVerify(dp);
return dp[weight.length - 1][bagSize];
}
public static void testAndVerify(int[][] dp){
//验证dp数组
System.out.println(Arrays.deepToString(dp));
}
}
这里其实可以发现最简单的是推导公式了,推导公式估计看一遍就记下来了,但难就难在如何初始化和遍历顺序上。