动态规划:01背包理论基础(一)
背包分类图
什么是01背包?
01背包
有n
件物品和一个最多能背重量为w
的背包。第i件物品的重量是weight[i]
,得到的价值是value[i]
。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
关于其他背包
- 除01背包以外其他类型的背包,面试几乎不会问,都是竞赛级别的了,leetcode上连多重背包的题目都没有,所以题库也告诉我们,01背包和完全背包就够用了。
- 而完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。
- 所以背包问题的理论基础重中之重是01背包,一定要理解透!
举个栗子
weight = [1, 3, 4]
value = [15, 20, 30]
注:下面所出现的数字都以此例子为例
二维dp数组01背包
动态规划五步曲:
- 确定dp数组以及下标的含义
我们有两个维度需要分别表示:物品和背包容量,即有0-i个放入j容量的背包所拿到的最大价值,其中0-i个物品皆可选择是否放入,且物品唯一,如下图:
(如果想用j 表示物品,j表示背包容量 行不行? 都可以的,个人习惯而已)
然后我们来逐一分析一下:
首先是把物品0放入背包的情况,weight[0] = 1, value[0] = 15:
背包容量为0,放不下物品0,此时背包里的价值为0。
背包容量为1,可以放下物品0,此时背包里的价值为15.
背包容量为2,依然可以放下物品0 (注意 01背包里物品只有一个),此时背包里的价值为15。
以此类推。
然后是0物品和1物品同时有的情况:
背包容量为 0,放不下物品0 或者物品1,此时背包里的价值为0。
背包容量为 1,只能放下物品0,背包里的价值为15。
背包容量为 2,只能放下物品0,背包里的价值为15。
背包容量为 3,上一行同一状态,背包只能放物品0,这次也可以选择物品1了,背包可以放物品1 或者 物品0,物品1价值更大,背包里的价值为20。
背包容量为 4,上一行同一状态,背包只能放物品0,这次也可以选择物品1了,背包可以放下物品0 和 物品1,背包价值为35。
通过这个举例,我们来进一步明确dp数组的含义。
即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
- 确定递推公式
对于递推公式,首先我们要明确有哪些方向可以推导出dp[i][j]
。
这里我们以dp[1][4]
为例:
首先我们有物品0和物品1,dp[1][4]
有两种情况:放物品1?还是不放物品1?
如果不放
物品1,则背包价值应该为dp[0][4]
,如果放
物品1,则我们应该预先留出放物品1的空间,则此时的j
为4-weight[1]
,且我们是没有放物品1的,则此时的i
为i-1
,则我们推出了两种dp[1][4]
的来源,此时我们只需要取其最大价值即可。即递推方程为:
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。如图:
状态转移方程 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物品。
代码如下:
1 | //在创建数组时就已经初始为0了 ,可以省略 |
结果如下图:
- 确定遍历顺序
由递推公式可知dp[i][j]由它二维数组的左上方推演而来,则其先遍历背包容量或者先遍历物品都是可以的,看自己习惯。
- 举例推导dp数组
自己在纸上推演,再来写代码,结果如图:
代码实现
1 | import java.util.Scanner; |