微信制作网站,做网站选什么配置电脑,用wordpress做论坛好吗,装饰公司网页设计前言
又是一次漫长的更新#xff08;我真不是故意的aaaaaaaaaaaaaaa#xff09;#xff0c;先不多说了#xff0c;直接给我~坐下~说错了说错了#xff0c;直接开始~
背包问题----动态规划
背包问题#xff08;knapsack problem#xff09;
动态规划#xff08;dyna…前言
又是一次漫长的更新我真不是故意的aaaaaaaaaaaaaaa先不多说了直接给我~坐下~说错了说错了直接开始~
背包问题----动态规划
背包问题knapsack problem
动态规划dynamic programming
01背包可行性 对一个背包最多载重m斤共有n件物品第i件物品重量为w[i]。对每件物品可选择拿走或不拿。请问能否恰好拿到总重量为m斤 01决策不选0选1
凑数可行性 目标凑出数字m有n个数字可以使用第i个数字为x[i]。对每一个数字最多可以选用1次。请问能否恰好凑出数字m 01决策不选0选1
简化问题 01背包可行性 f[i][j]表示只用前i个数字能否凑出j 初始条件
f[0][0]1
状态转移方程
若jx[i]——f[i][j]f[i-1][j]
若jx[i]——f[i][j]f[i-1][j]或f[i-1][j-x[i]]
01背包3种问题
可行性判定问题
用n个物品能否恰好凑出m斤重量
方案计数问题
用n个物品能否恰好凑出m斤各种方案
最优化问题
用n个物品凑出不超过m斤时最多几斤
01背包 关于01背包建议结合我的B站视频一起学习相信会对你彻底理解背包问题有很大帮助 带你学透0-1背包问题| 关于背包问题你不清楚的地方这里都讲了| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibiliwww.bilibili.com/video/BV1cg411g7Y6编辑https://link.zhihu.com/?targethttps%3A//www.bilibili.com/video/BV1cg411g7Y6带你学透01背包问题滚动数组篇 | 从此对背包问题不再迷茫_哔哩哔哩_bilibiliwww.bilibili.com/video/BV1BU4y177kY编辑https://link.zhihu.com/?targethttps%3A//www.bilibili.com/video/BV1BU4y177kY 有N件物品和一个最多能被重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 这是标准的背包问题以至于很多混丝看了这个自然就会想到背包甚至都不知道暴力的解法应该怎么解了。
这样其实是没有从底向上去思考而是习惯性想到了背包那么暴力的解法应该是怎么样的呢 每一件物品其实只有两个状态取或者不取所以可以使用回溯法搜索出所有的情况那么时间复杂度就是O(2^n)这里的n表示物品数量。 二维dp数组01背包
确定dp数组以及下标的含义
对于背包问题有一种写法 是使用二维数组即dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少
要时刻记着这个dp数组的含义下面的一些步骤都围绕这dp数组的含义进行的如果哪里看懵了就来回顾一下i代表什么j又代表什么。
确定递推公式
再回顾一下dp[i][j]的含义从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]
由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值 所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); dp数组如何初始化
关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。
状态转移方程 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 可以看出i 是由 i-1 推导出来那么i为0的时候就一定要初始化。
dp[0][j]即i为0存放编号0的物品的时候各个容量的背包所能存放的最大价值。
代码如下
for (int j weight[0]; j bagWeight; j) {dp[0][j] value[0];
}
dp[0][j] 和 dp[i][0] 都已经初始化了那么其他下标应该初始化多少呢
dp[i][j]在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了因为0就是最小的了不会影响取最大价值的结果。
如果题目给的价值有负数那么非0下标就要初始化为负无穷了。例如一个物品的价值是-2但对应的位置依然初始化为0那么取最大值的时候就会取0而不是-2了所以要初始化为负无穷。
而背包问题的物品价值都是正整数所以初始化为0就可以了。
这样才能让dp数组在递归公式的过程中取最大的价值而不是被初始值覆盖了。
最后初始化代码如下
vectorvectorint dp(weight.size() 1, vectorint(bagWeight 1, 0));
for (int j weight[0]; j bagWeight; j) {dp[0][j] value[0];
} 那么问题来了先遍历物品还是先遍历背包重量呢 其实都可以 但是先遍历物品更好理解。
那么我先给出先遍历物品然后遍历背包重量的代码。
// weight数组的大小 就是物品个数
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]; // 这个是为了展现dp数组里元素的变化else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}
} 先遍历背包再遍历物品也是可以的
例如这样
// weight数组的大小 就是物品个数
for(int j 0; j bagWeight; j) { // 遍历背包容量for(int i 1; i weight.size(); i) { // 遍历物品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]);}
}
为什么也是可以的呢
要理解递归的本质和递推的方向。
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]的左上角方向包括正左和正上两个方向 其实背包问题里两个for循环的先后循序是非常有讲究的理解遍历顺序其实比理解推导公式难多了。 总结
讲了这么多才刚刚把二维dp的01背包讲完这里大家其实可以发现最简单的是推导公式了推导公式估计看一遍就记下来了但难就难在如何初始化和遍历顺序上。
可能有的混丝并没有注意到初始化和遍历顺序的重要性我们后面做力扣上背包面试题目的时候大家就会感受出来了。
这真是n年一度的大更新
