您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
背包问题九讲 背包问题例子
背包,遍历,物品背包问题九讲 背包问题例子
发布时间:2020-12-06加入收藏来源:互联网点击:
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[i][j]所需要的数据就是左上角,根本不影响dp[i][j]公式的推导!
但先遍历物品再遍历背包这个顺序更好理解。
其实背包问题里,两个for循环的先后循序是非常有讲究的,理解遍历顺序其实比理解推导公式难多了。
举例推导dp数组来看一下对应的dp数组的数值,如图:
最终结果就是dp[2][4]。
建议大家此时自己在纸上推导一遍,看看dp数组里每一个数值是不是这样的。
做动态规划的题目,最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下,然后在动手写代码!
很多同学做dp题目,遇到各种问题,然后凭感觉东改改西改改,怎么改都不对,或者稀里糊涂就改过了。
主要就是自己没有动手推导一下dp数组的演变过程,如果推导明白了,代码写出来就算有问题,只要把dp数组打印出来,对比一下和自己推导的有什么差异,很快就可以发现问题了。
相信很多小伙伴刷题的时候面对力扣上近两千到题目,感觉无从下手,我花费半年时间整理的github学习项目leetcode刷题指南:https://github.com/youngyangyang04/leetcode-master,不仅有详细经典题目刷题顺序而且对应题解来排好了,难点还有视频讲解,按照list一道一道刷就可以了,绝对值得star一波!
完整C++测试代码voidtest_2_wei_bag_problem1(){vectorintweight={1,3,4};vectorintvalue={15,20,30};intbagWeight=4;//二维数组vectorvectorintdp(weight.size()+1,vectorint(bagWeight+1,0));//初始化for(intj=bagWeight;j=weight[0];j--){dp[0][j]=dp[0][j-weight[0]]+value[0];}//weight数组的大小就是物品个数for(inti=1;iweight.size();i++){//遍历物品for(intj=0;j=bagWeight;j++){//遍历背包容量if(jweight[i])dp[i][j]=dp[i-1][j];elsedp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}coutdp[weight.size()-1][bagWeight]endl;}intmain(){test_2_wei_bag_problem1();}以上遍历的过程也可以这么写:
//遍历过程for(inti=1;iweight.size();i++){//遍历物品for(intj=0;j=bagWeight;j++){//遍历背包容量if(j-weight[i]=0){dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}}这么写打印出来的dp数据这就是这样:
空出来的0其实是用不上的,版本一 能把完整的dp数组打印出来,出来我用版本一来讲解。
总结讲了这么多才刚刚把二维dp的01背包讲完,这里大家其实可以发现最简单的是推导公式了,推导公式估计看一遍就记下来了,但难就难在如何初始化和遍历顺序上。
可能有的同学并没有注意到初始化 和 遍历顺序的重要,我们后面做力扣上背包面试题目的时候,大家就会感受出来了。
下一篇,我们再来讲一维dp数组实现的01背包(滚动数组),分析一下和二维有什么区别,在初始化和遍历顺序上又有什么差异,敬请期待!
我是程序员Carl,个人主页:https://github.com/youngyangyang04
这里每天8:35准时推送一道经典算法题目,我选择的每道题目都不是孤立的,而是由浅入深,环环相扣,帮你梳理算法知识脉络,轻松学算法!
@代码随想录 期待你的关注
我花了半年时间,整理的力扣刷题攻略,已经全部发布在Github上,点击下方链接查看吧!
本文到此结束,希望对大家有所帮助呢。
上一篇:(樵叶蜂)-昆虫记樵叶蜂
下一篇:返回列表
相关链接 |
||
网友回复(共有 0 条回复) |