三丰云做网站教程,网站备案幕布申请,织梦cms做网站怎么样,商城类网站建设多少钱01背包问题 二维 代码随想录 视频讲解#xff1a;带你学透0-1背包问题#xff01;| 关于背包问题#xff0c;你不清楚的地方#xff0c;这里都讲了#xff01;| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili 1.dp数组定义
dp[i][j] 下标为[0,i]之间的物品…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(iweight.size() ) 物品 for(jbagweight ) 背包
对于二维数组实现的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(iweight.size()) 物品 for(jbagweight,jweight[0] ) 背包
采用倒序是为了防止物品重复选取比较的数据来自上一轮
正序遍历就是用同一个物品塞满背包每次覆盖的数据都是同一个物品塞满的情况 dp【i】【j】的更新只与dp【i-1】【j】和dp【i-1】【j-weight_i】左上角这两个数据有关而与右边的数据无关那么从右向左遍历遍历时左边的数据还是上一行的数据没有更新 这样子用一行数组很好的实现了我们的最终目的 在一维中只能先遍历物品再遍历背包
如果先遍历背包再遍历物品那记录的就是只有一个物品 416. 分割等和子集 代码随想录 视频讲解动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集_哔哩哔哩_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(vectorint nums) {int sum 0;for(int i: nums)sumi;if(sum%2!0) return false;int target sum/2;vectorint dp(target1,0);for(int i0 ; i nums.size(); i) //物品{for(int j target; jnums[i] ; j--) //背包{dp[j] max(dp[j], dp[j- nums[i] ] nums[i] ); //这题物品和价值是一样的}}if(dp[target]target) return true;else return false;}
};
收获
今天掌握了01背包的理论基础本尝试应用
