01 背包题目分析
有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i],得到的价值是 value[i]。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是 O(2^n),这里的 n 表示物品数量。
暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化!
在下面的讲解,举一个例子:
| 重量 | 价值 | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
01 背包解决方法
递归五部曲
- 确定 dp 数组以及下标的含义:dp[i][j] 表示从下标为 [0-i] 的物品里任意取,放进容量为 j 的背包,价值总和最大是多少。
为什么需要用二维数组呢?因为有两个维度需要分别表示:物品和背包容量。
我们先看把物品 0 放入背包的情况:
背包容量为 0,放不下物品 0 或者物品 1,此时背包里的价值为 0。
背包容量为 1,只能放下物品 0,背包里的价值为 15。
背包容量为 2,只能放下物品 0,背包里的价值为 15。
背包容量为 3,上一行同一状态,背包只能放物品 0,这次也可以选择物品 1 了,背包可以放物品 1 或者物品 0,物品 1 价值更大,背包里的价值为 20。
背包容量为 4,上一行同一状态,背包只能放物品 0,这次也可以选择物品 1 了,背包可以放下物品 0 和物品 1,背包价值为 35。
- 确定递推公式
对于递推公式,首先我们要明确有哪些方向可以推导出 dp[i][j]。
这里我们 dp[1][4] 的状态来举例:
求取 dp[1][4] 有两种情况:
- 放物品 1
- 还是不放物品 1
如果不放物品 1,那么背包的价值应该是 dp[0][4] 即容量为 4 的背包,只放物品 0 的情况。
如果放物品 1,那么背包要先留出物品 1 的容量,目前容量是 4,物品 1 的容量(就是物品 1 的重量)为 3,此时背包剩下容量为 1。
容量为 1,只考虑放物品 0 的最大价值是 dp[0][1],这个值我们之前就计算过。
所以放物品 1 的情况 = dp[0][1] + 物品 1 的价值。
两种情况综合一起可以得出:
递归公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
- dp 数组初始化
首先从 dp[i][j] 的定义出发,如果背包容量 j 为 0 的话,即 dp[i][0],无论是选取哪些物品,背包价值总和一定为 0。
从递归公式可以看出 i 是由 i-1 推导出来,那么 i 为 0 的时候就一定要初始化。
- 确定遍历顺序
先遍历物品还是先遍历背包重量呢?
其实都可以!但是先遍历物品更好理解。
那么我先给出先遍历物品,然后遍历背包重量的代码。
for(int i = 1; i < n; i++) {
for(int j ; j <= bagweight; j++) {
(j < weight[i]) {
dp[i][j] = dp[i - ][j];
} {
dp[i][j] = Math.max(dp[i - ][j], dp[i - ][j - weight[i]] + value[i]);
}
}
}


