01背包问题 二维
代码随想录视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili
1.dp数组定义
dp[i][j] 下标为[0,i]之间的物品,任取放容量为j的背包的最大价值
2.递推公式
不放物品i: dp[i-1][j] 去看是否放i-1,还是有j的容量给i-1去放
放物品i : dp[i-1][j-weight[i]] + value[i],放了物品i,那么就只有j-weight[i]的容量给i-1个物品去放了,同时要加上我这个物体的价值
dp[i][j] = max(上面两个),取最大价值
3.数组初始化
首先看,i是由i-1推出来的,j是否左上的某一个格子或者正上推出来的(背包剩余容量)
dp[i][0] = 0,背包的容量为0,不管放哪个,价值都为0
dp[0][j] , 当背包可以装下这个物品开始,dp[0][j]就等于这个物品的价值,装不下就为0
4.遍历顺序
for(i<weight.size() ) 物品
for(j<=bagweight ) 背包
对于二维数组实现的01背包,物品和背包的遍历顺序是可以颠倒的,因为左上方和上方是有值的
循环体内是正序还是倒序都是可以的,因为都是根据上一行的数据来进行推导的
01背包问题 一维
代码随想录视频讲解:带你学透01背包问题(滚动数组篇) | 从此对背包问题不再迷茫!_哔哩哔哩_bilibili
因为这里的i层都是由i-1层推到出来的,因此只需要一个一行的一维滚动数组来维护就可以了,不需要整个二维数组
1. dp[j] 容量为j的背包的最大价值为dp[j]
2.递推公式
不放物品i,就是自己dp[j],也就是把上一层数据拷贝下来
放物品i , dp[j-weight[i]] + value[i]
dp[j] = max(上面两个)
3.初始化
dp[0]=0 , 背包容量为0的时候,最大价值为0
非零下标都是初始化为0,因为为其他的话,会覆盖掉递推公式中算出来的值
4.遍历顺序
for(i<weight.size()) 物品
for(j=bagweight,j>=weight[0] ) 背包
采用倒序,是为了防止物品重复选取,比较的数据来自上一轮
正序遍历就是用同一个物品塞满背包,每次覆盖的数据都是同一个物品塞满的情况
dp【i】【j】的更新只与dp【i-1】【j】和dp【i-1】【j-weight_i】左上角这两个数据有关,而与右边的数据无关,那么从右向左遍历,遍历时左边的数据还是上一行的数据没有更新, 这样子用一行数组很好的实现了我们的最终目的
在一维中,只能先遍历物品,再遍历背包
如果先遍历背包,再遍历物品,那记录的就是只有一个物品
416. 分割等和子集
代码随想录视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili
解题思路
本题元素只能使用1次,并且看能不能装满11这个背包
1.dp[j] 容量为j的背包的最大价值,本题最大价值和重量,都是数字本身
2. dp[j] = max(dp[j], dp[j-nums[i] + nums[i]])
3.dp[0] = 0;非零下标,初始为非负整数的最小值,也就是0,因为是由max得来的
4.遍历顺序,先遍历物品,再遍历背包,背包是倒序,j要大于等于nums[i],且每个物品只能使用一次
最后去判断背包是否装满了 dp[target] == target
class Solution {
public:bool canPartition(vector<int>& nums) {int sum =0;for(int i: nums)sum+=i;if(sum%2!=0) return false;int target = sum/2;vector<int> dp(target+1,0);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;else return false;}
};
收获
今天掌握了01背包的理论基础,本尝试应用