代码随想录算法训练营第四十四天 | 01背包问题 二维、 01背包问题 一维、416. 分割等和子集

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背包的理论基础，本尝试应用