文章参考来源代码随想录
题目参考来源leetcode
01背包问题 二维:
背包问题:
动规五部曲:
1.确定dp数组以及下标的含义:
其实这里由题目要我们求的就可以推出来了
把下标为0-i的物品装入容量为j的背包最大价值为dp[i][j]。
具体分析:
我们需要使用二维数组,为什么呢?
因为有两个维度需要分别表示:物品 和 背包容量
如图,二维数组为 dp[i][j]。
那么这里 i 、j、dp[i][j] 分别表示什么呢?
i 来表示物品、j表示背包容量。
我们来尝试把上面的 二维表格填写一下。
动态规划的思路是根据子问题的求解推导出整体的最优解。
我们先看把物品0 放入背包的情况:
背包容量为0,放不下物品0,此时背包里的价值为0。
背包容量为1,可以放下物品0,此时背包里的价值为15.
背包容量为2,依然可以放下物品0 (注意 01背包里物品只有一个),此时背包里的价值为15。
以此类推。
再看把物品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[1][4] 表示什么意思呢。
任取 物品0,物品1 放进容量为4的背包里,最大价值是 dp[1][4]。
通过这个举例,我们来进一步明确dp数组的含义。
即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少。
2.确定递推公式:
当前背包容量为j放入物品i,这里可以分成两种情况:
背包空间不够放入物品i:取不放物品i时的最大价值dp[i-1][j];
足够放入物品i:比较不放物品i时的最大价值dp[i-1][j]和放入后的总价值dp[i-1][j-weigh[i]]+value[i];
(可以理解为没放入之前已有的最大价值dp[i-1][j-weigh[i]]加上当前物品的价值)因此这里的递推公式为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
具体分析:
首先我们要明确有哪些方向可以推导出 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 的价值,推导方向如图:
两种情况,分别是放物品1 和 不放物品1,我们要取最大值(毕竟求的是最大价值)
dp[1][4] = max(dp[0][4], dp[0][1] + 物品1 的价值)
3.dp数组如何初始化:
第一列:表示背包容量为0时放入下标0到i的物品,无意义,因此第一列不用初始化(或者全初始化为0)
第一行:表示背包容量为0到j时放入下标为0的物品,当背包容量大于物品0的重量时,才能放入。因此这里从物品0的重量到背包总重量全都初始化为物品0的价值
4.确定遍历顺序:
在如下图中,可以看出,有两个遍历的维度:物品与背包重量
那么问题来了,先遍历 物品还是先遍历背包重量呢
其实都可以(虽然两个for循环遍历的次序不同,其实根本不影响dp[i][j]公式的推导), 但是先遍历物品更好理解。(把物品i放入背包容量从0到背包总重所能存入的最大价值)
注意这里物品从1开始遍历,因为物品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]的左上角方向(包括正上方向),那么先遍历物品,再遍历背包的过程如图所示:
5.举例推导dp数组:
来看一下对应的dp数组的数值,如图:
最终结果就是dp[2][4]。
#include <bits/stdc++.h>
using namespace std;
int main(){int n,bagw;cin>>n>>bagw;vector<int>value(n,0) ;vector<int>weigh(n,0);for(int i=0;i<n;i++)cin>>weigh[i];for(int i=0;i<n;i++)cin>>value[i];vector<vector<int>>dp(n,vector<int>(bagw+1,0));for(int j=weigh[0];j<=bagw;j++){dp[0][j]=value[0];}for(int i=1;i<n;i++){for(int j=0;j<=bagw;j++){if(j-weigh[i]<0)dp[i][j]=dp[i-1][j];else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weigh[i]]+value[i]);}}cout<< dp[n-1][bagw]<<endl; return 0;
}
01背包问题 一维:
对于背包问题其实状态都是可以压缩的。
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上,表达式完全可以是:dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上,不如只用一个一维数组了,只用dp[j](一维数组,也可以理解是一个滚动数组)。
动规五部曲:
1.确定dp数组以及下标的含义:
dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少
在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]
2.确定递推公式:
二维dp数组的递推公式为:dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
一维把物品下标优化掉了,直接把上一层的拷贝到这一层就好了,
所以在 上面递推公式的基础上,去掉i这个维度就好。
dp[j] = max(dp[j], dp[j] -weight[i]] + value[i])
3.dp数组如何初始化:
关于初始化,一定要和dp数组的定义吻合,否则到递推公式的时候就会越来越乱。
dp在推导时一定取的是最大值,如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。这样才能让dp数组在递归公式的过程中取的最大的价值,而不是被初始值覆盖了。
因此全部初始化为0
4.确定遍历顺序:
这里和二维有比较大的区别了
首先这里在遍历背包时要从大(背包总重)到小(物品i的重量)以保证物品i只被放入一次
如果正序遍历
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
所以从后往前循环,每次取得状态不会和之前取得状态重合,这样每种物品就只取一次了。
而对于二维dp,dp[i][j]都是通过上一层即dp[i - 1][j]计算而来,本层的dp[i][j]并不会被覆盖
因此这里二维遍历背包时是要从0到背包总重(如果从物品i重量到背包总重的话,遍历下一层/下一个物品时会出现上一层没有数据可以用的情况)
以及物品从下标0开始遍历,因为二维初始化了第一行,而一维创建数组的时候默认为0了,所以这里是没有遍历过物品0的
代码中是先遍历物品嵌套遍历背包容量的,如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。
5.举例推导dp数组:
一维dp,分别用物品0,物品1,物品2 来遍历背包,最终得到结果如下:
#include <bits/stdc++.h>
using namespace std;
int main(){int n,bagw;cin>>n>>bagw;vector<int>value(n,0) ;vector<int>weigh(n,0);for(int i=0;i<n;i++)cin>>weigh[i];for(int i=0;i<n;i++)cin>>value[i];vector<int>dp(bagw+1,0);for(int i=0;i<n;i++){for(int j=bagw;j>=weigh[i];j--){dp[j]=max(dp[j],dp[j-weigh[i]]+value[i]);}}cout<< dp[bagw]<<endl; return 0;
}
416. 分割等和子集
背包问题有多种背包方式,常见的有:01背包、完全背包、多重背包、分组背包和混合背包等等。
要注意题目描述中商品是不是可以重复放入。
即一个商品如果可以重复多次放入是完全背包,而只能放入一次是01背包,写法还是不一样的。
要明确本题中我们要使用的是01背包,因为元素我们只能用一次。
这道题目是要找是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
那么只要找到集合里能够出现 sum / 2 的子集总和,就算是可以分割成两个相同元素和子集了。
只有确定了如下四点,才能把01背包问题套到本题上来。
- 背包的容量为sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
以上分析完,我们就可以套用01背包,来解决这个问题了。
动规五部曲:
1.确定dp数组以及下标的含义:
dp[j]表示 背包总容量(所能装的总重量)是j,放进物品后,背的最大重量(之前这里是价值)为dp[j]。
那么如果背包容量为target, dp[target]就是装满 背包之后的重量(之前这里是价值),所以 当 dp[target] == target 的时候,背包就装满了。(因为本题元素价值就是重量)理解这点很重要
装不满的情况:
拿输入数组 [1, 5, 11, 5],举例, dp[7] 只能等于 6,因为 只能放进 1 和 5。
而dp[6] 就可以等于6了,放进1 和 5,那么dp[6] == 6,说明背包装满了。
2.确定递推公式:
01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。
所以递推公式:dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.dp数组如何初始化:
本题题目中 只包含正整数的非空数组,所以非0下标的元素初始化为0就可以了
4.确定遍历顺序:
具体见上题
5.举例推导dp数组:
dp[j]的数值一定是小于等于j的。
如果dp[j] == j 说明,集合中的子集总和正好可以凑成总和j,理解这一点很重要。
用例1,输入[1,5,11,5] 为例,如图:
最后dp[11] == 11,说明可以将这个数组分割成两个子集,使得两个子集的元素和相等。
class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;vector<int>dp(10001,0);for (int i = 0; i < nums.size(); i++) {sum += nums[i];}if(sum%2==1)return false;int target=sum/2;for(int i=0;i<nums.size();i++){for(int j=target;j>=nums[i];j--){dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}return dp[target] == target? true:false;}
};