背包问题的重中之重是01背包
01背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是o(2^n),这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化!
举一个例子:背包最大重量为4,有3个物品,其重量和价值如下表
物品为:
重量 | 价值 | |
---|---|---|
物品0 | 1 | 15 |
物品1 | 3 | 20 |
物品2 | 4 | 30 |
问背包能背的物品最大价值是多少?
动规五部曲
对于背包问题,有一种写法, 是使用二维数组,即dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少,i代表第几个物品,j代表背包的容量,dp[i][j]代表价值
2)递推公式
对于每一个物品都有放与不放两种状态,所以又有两种情况,取这两种情况的最大值
根据递推公式,可知dp数组是由其左上角和正上方推导而来,所以要对其第一行和第一列进行初始化
其他下标的价值由递推公式更新推导,所以其它地方初始化为任意值均可
因为本题有两个维度,分别为物品维度和背包容量维度,所以到底是先遍历物品呢?还是先遍历背包呢?
可以分类讨论一下
先遍历物品
先遍历背包
5)打印dp数组
int weight_bag(vector<int> weight,vector<int> value,int bagweight){
vector<vector<int>> dp(weight.size(),vector<int>(bagweight+1,0));
//初始化.对于物品0
for(int j=weight[0];j<=bagweight;j++){
dp[0][j]=value[0];
}
//递推(先遍历物品,再遍历背包)
for(int i=1;i<weight.size();i++){
for(int j=0;j<=bagweight;j++){
if(j<weight[i]) dp[i][j]=dp[i-1][j];//如果当前物品重量比背包容量大,则装不下该物品
//如果当前物品重量比背包容量小,那么可以有两种选择,装下该物品,或是不装该物品
else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
return dp[weight.size()-1][bagweight];
}
01背包(滚动数组)
把dp[i – 1]这一层拷贝到dp[i]上,只用一个一维数组dp[j],可以理解是一个滚动数组。
滚动数组需要满足的条件是上一层可以重复利用,直接拷贝到当前层,一直处于一种刷新的状态
动规五部曲
1)确定dp数组的定义
在一维dp数组中,dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]。
2)一维dp数组的递推公式
dp[j]有两个选择,一个是不放物品i,取自己dp[j] 相当于 二维dp数组中的dp[i-1][j];一个是放物品i,取dp[j – weight[i]] + value[i],取二者当中的最大值
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3)一维dp数组的初始化
dp[0]就应该是0,因为背包容量为0所背的物品的最大价值就是0。
根据递推公式,dp数组在推导的时候一定是取价值最大的数,那么非0下标都初始化为0就可以了,这样才能让dp数组在递归公式的过程中取的最大的价值,而不是被初始值覆盖了。
一维dp遍历的时候,背包是从大到小,注意一定要是倒序遍历
倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次!
因为根据递推公式,每个物品只放一次,在遍历物品的时候,变动j时,每次都要刷新dp[j]
dp[1]=dp[1-weight[0]]+value[0]=dp[0]+15=0+15=15
dp[2]=dp[2-weight[0]]+value[0]=dp[1]+value[0]=15+15=30,这里物品0会放入两次,因为前面刷新了dp[1],初始值会被修改,连带着后面的dp[2]会受到波及!!!!
为什么二维dp数组遍历的时候不用倒序呢?
因为对于二维dp,dp[i][j]都是通过上一层即dp[i – 1][j]计算而来,本层的dp[i][j]并不会被覆盖!,因为是二维数组,没有动态刷新,所以一旦求出数值,便会一直在那保持不变
两个嵌套for循环的顺序,代码中是先遍历物品嵌套遍历背包容量,那可不可以先遍历背包容量嵌套遍历物品呢?
不可以!因为一维dp的写法,背包容量一定是要倒序遍历(原因上面已经写了),如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。
因为是每次只对一个背包容量进行求解,
dp[4]=dp[4-1]+value[0]=15
dp[4]=max(15,dp[4-3]+value[1])=max(15,20)=20
dp[4]=max(10,dp[4-4]+value(2))=max(20,30)=30
dp[3]=dp[3-1]+value(0)=value(0)=15
……..
如上,因为是倒序遍历和初始化的存在,针对每个背包容量,每次都只放进了一个物品,不能将两个或多个物品的情况考虑在内
dp[4]=dp[4-1]+value[0]=15
dp[3]=max(dp[3],dp[3-1]+value[0])=15
dp[2]=max(dp[2],dp[2-1]+value[0])=15
dp[1]=max(dp[1],dp[1-1]+value[0])=15
dp[4]=max(dp[4],dp[4-3]+value[1])=max(15,15+20)=35
………
如上,每个背包的容量随着物品的变动与前面每一个物品的情况结合起来,这才是正解
倒序遍历的原因是,本质上还是一个对二维数组的遍历,并且右下角的值依赖上一层左上角的值,因此需要保证左边的值仍然是上一层的,从右向左覆盖。
倾向于使用一维dp数组的写法,比较直观简洁,而且空间复杂度还降了一个数量级!
int weightvalue(int bagweight,vector<int>weight,vector<int>value){
//初始化dp数组
vector<int> dp(bagweight+1,0);
//递推
for(int i=0;i<weight.size();i++){
for(int j=bagweight;j>=weight[i];j--){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[bagweight];
}
题目:416分割等和子集
题目链接:分割等和子集
对题目的理解
非空数组由正整数组成,是否可以将这个数组分割成两个子集,使得两个子集的元素和相等
将问题具象化:只要找到集合里能够出现 sum / 2 的子集总和,就算是可以分割成两个相同元素和子集了。
集合中的元素只能使用一次,因此使用的是01背包
只有确定了如下四点,才能把01背包问题套到本题上来。
动规五部曲
1)确定dp数组含义及下标
dp[j]:容量为j的背包所背的最大价值为dp[j]
集合中的每个元素既是重量也是价值 dp[target]==target 背包装满 其中target=sum/2
2)递推公式
背包的递推公式:dp[j]=max(dp[j],dp[j-weight[i]]+value[i])
所以本题的递推公式:dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
3)dp数组初始化
dp[0]=0 ,非零下标进行初始化,dp[i]=0,根据递推公式,不能初始化别的值,初始化为非负整数的最小值,即0,这样才能让dp数组在递推的过程中取得最大的价值,而不是被初始值覆盖了。
4)遍历顺序
for(i=0;i<nums.size(i++)){
5)打印dp数组
class Solution {
public:
bool canPartition(vector<int>& nums) {
vector<int> dp(10001,0);//定义dp数组,并将其初始化为0,因为数组中的元素最大是100,且至少有200个数那么最大的重量为200*100=20000,背包中只有一半容量就可以了
int sum = 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]);
}
}
if(dp[target]==target) return true;
return false;
}
};
原文地址:https://blog.csdn.net/qq_43773652/article/details/134613893
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_4473.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!