动态规划-01背包理论基础(二)
上一篇我们提到了01背包的二维的dp数组,这篇我们就来说一说01背包的一维数组,也就是滚动数组,为什么叫滚动数组看完接下来的分析你就懂了!
那么我们通过01背包,来彻底讲一讲滚动数组!
接下来还是用如下这个例子来进行讲解:
weight = [1, 3, 4]
value = [15, 20, 30]
一维dp数组(滚动数组)
对于背包问题其实状态都是可以压缩的!
在使用二维数组的时候,递推公式:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
;
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上,即利用上一层的数据将二维表达式里的dp[i-1][j]直接用上一次遍历的结果,即数组进行了一个滚动操作,表达式完全可以是:dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])
;
与其把dp[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组)
注:我们千万不能忘记dp[i][j]的含义!dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
动态规划五步曲
- 确定dp数组的定义
dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。
- 一维dp数组的递推公式
二维dp数组的递推公式为: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
以下为分析:
-
dp[j]为 容量为j的背包所背的最大价值。
-
dp[j]可以通过dp[j - weight[i]]推导出来,dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
-
dp[j - weight[i]] + value[i] 表示 容量为 [j - 物品i重量] 的背包加上物品i的价值。(也就是容量为j的背包,放入物品i了之后的价值即:dp[j])
-
此时dp[j]有两个选择,一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j],即不放物品i,一个是取dp[j - weight[i]] + value[i],即放物品i,指定是取最大的,毕竟是求最大价值。
- 一维dp数组如何初始化
dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j],那么dp[0]就应该是0,因为背包容量为0所背的物品的最大价值就是0。
那么dp数组除了下标0的位置,初始为0,其他下标应该初始化多少呢?
看一下递归公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
;
dp数组在推导的时候一定是取价值最大的数,如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取的最大的价值,而不是被初始值覆盖了。
那么我假设物品价值都是大于0的,所以dp数组初始化的时候,都初始为0就可以了。
- 一维dp数组遍历顺序
代码如下:
1 | for(int i = 0; i < weight.size(); i++) { // 遍历物品 |
这里大家发现和二维dp的写法中,遍历背包的顺序是不一样的!二维dp遍历的时候,背包容量是从小到大,而一维dp遍历的时候,背包是从大到小。
为什么呢?**倒序遍历是为了保证物品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
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
再来看看两个嵌套for循环的顺序,代码中是先遍历物品嵌套遍历背包容量,那可不可以先遍历背包容量嵌套遍历物品呢?
不可以!
因为一维dp的写法,背包容量一定是要倒序遍历(原因上面已经讲了),如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。
**所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的!**这一点大家一定要注意。
- 举例推导dp数组
一维dp,分别用物品0,物品1,物品2 来遍历背包,最终得到结果如下:
像不像二维数组的每条都滚动展示!
代码实现
1 | import java.util.Scanner; |
v1.5.1