当前位置: 首页 > 科技观察

0-1背包问题,你应该知道!

时间:2023-03-17 14:20:50 科技观察

关于01的背包问题,你应该知道!这周我们正式开始讲解背包问题!不过说实话,背包九讲对小白来说确实不友好,看起来还是有点吃力,而且都是假代码,也很难看懂。面试的话,其实掌握01背包和completebackpack就够了,顶多加一个multi-pack就可以了。如果你分不清这几种背包的区别,我在这里画了一张图,如下:SegmentationandSubset1至于BackpacksLecture9中的其他背包,面试几乎不会问他们,都是在比赛层面。leetcode上连多个backpack都没有一道题,所以题库也告诉我们01backpack和completebackpack就够了。完整背包也是01背包的一个小改动,那就是:完整背包的物品数量是无限的。所以,背包问题最重要的理论基础就是01背包问题,一定要理解透彻!leetcode上没有纯01背包问题,都是01背包应用问题,也就是需要转化为01背包问题。所以我先通过纯01背包问题把01背包的原理说清楚。后面讲解leetcode问题的时候,重点是如何转化为01背包问题。之前可能有的记录者已经可以熟练的写背包了,但是只要你认真看完这篇文章,相信你会有意想不到的收获!01背包里有n件物品和一个最大重量为w的背包。第i个物品的权重为weight[i],得到的值为value[i]。每个物品只能使用一次,找出总价值最大的物品放入背包。动态规划-背包问题这是一个标准的背包问题,所以很多同学看了这个自然会想到背包,甚至不知道暴力解法怎么解。这么一来,我倒是没想到自下而上,而是习惯性的想到了背包,那么暴力解应该怎么办呢?每个item其实只有两种状态,take或者not,所以可以用回溯的方法搜索所有情况下,时间复杂度为,其中n代表item的个数。所以蛮力解决方案是指数时间复杂度。那么优化只需要动态规划的解法!在下面的解释中,我将举个例子:背包的最大重量是4。这些物品是:重量价值物品0115物品1320物品2430背包可以携带的物品的最大值是多少?以下解释和插图中出现的数字均基于此示例。二次元dp阵01背包还是一波五段解析。确定dp数组和下标的含义对于背包问题,有一种写法,就是用二维数组,即dp[i][j]表示取任意一个物品与下标[0-i],放入容量为j的背包中,最大值是多少。光是看这个二维数组的定义,大家就会有些疑惑。看下图:动态规划-背包问题1.永远记住这个dp数组的意义。下面的步骤都是围绕这个dp数组的意义展开的。如果你一头雾水,我们再回顾一下i代表什么,j代表什么。确定递归公式,复习dp[i][j]的含义:取任意下标为[0-i]的物品,放入容量为j的背包中,最大价值和为多少。那么有两个方向发射dp[i][j],不放itemi:从dp[i-1][j]发射,即背包容量为j,itemi的最大值不放在里面,此时dp[i][j]就是dp[i-1][j]。(实际上,当物品i的重量大于背包j的重量时,物品i无法放入背包,所以背包中的价值还是和之前一样。)放物品i:由dp[i-1][j-weight[i]]发射,背包容量为j-weight[i]时不放dp[i-1][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。如图:动态规划-背包问题2看其他情况。状态转移方程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的物品时,每个容量的背包可以存放的最大值。那么显然当j=weight[0]时,dp[0][j]应该是value[0],因为背包的容量足以装下0号物品。代码初始化如下:for(intj=0;j>dp(weight.size(),vector(bagweight+1,0));for(intj=weight[0];j<=bagweight;j++){dp[0][j]=value[0];}费了好大劲才解释怎么初始化。相信很多同学平时都是根据感觉来初始化dp数组的,但是有时候感觉是不靠谱的。确定遍历顺序如下图,可以看出遍历有两个维度:物品动态规划和背包重量-背包问题3那么问题来了,是先遍历物品还是先遍历背包重量应该先遍历?其实两者都可以!!但是先遍历这些项目才能更好地理解。那我先给出代码先遍历物品,再遍历背包重量。//权重数组的大小为item个数for(inti=1;iweight={1,3,4};vectorvalue={15,20,30};intbagweight=4;//二维数组vector>dp(weight.size(),vector(bagweight+1,0));//初始化for(intj=weight[0];j<=bagweight;j++){dp[0][j]=value[0];}//权重数组的大小为item个数for(inti=1;i