动态规划：关于01背包问题，你应该知道这个！

面试的话，其实掌握01背包和完整背包就够了，顶多加一个multi-pack。如果你分不清这几种背包的区别，我在这里画了一张图，如下：至于背包和其他背包，面试几乎不会问，都是比赛级别的，多背包问题不存在在leetcode上。所以题库也告诉我们01背包和fullbackpack就够了。完整背包也是01背包的一个小改动，那就是：完整背包的物品数量是无限的。所以，背包问题最重要的理论基础就是01背包问题，一定要理解透彻！leetcode上没有纯01背包问题，都是01背包应用问题，也就是需要转化为01背包问题。所以我先通过纯01背包问题把01背包的原理说清楚。后面讲解leetcode问题的时候，重点是如何转化为01背包问题。之前可能有的记录者已经可以熟练的写背包了，但是只要你认真看完这篇文章，相信你会有意想不到的收获！01背包里有N件物品和一个最多可以称W的背包，第i件物品的重量为weight[i]，得到的值为value[i]。每个物品只能使用一次，找出总价值最大的物品放入背包。这是一个标准的背包问题，所以很多同学看了这里自然会想到背包，连暴力解怎么解都不知道。这么一来，我倒是没想到自下而上，而是习惯性的想到了背包，那么暴力解应该怎么办呢？每个item其实只有两种状态，takeornot，所以可以用回溯的方法来搜索，所有情况下，时间复杂度都是O(2^n)，其中n代表item的个数。所以蛮力解决方案是指数时间复杂度。那么优化只需要动态规划的解法！在下面的解释中，我将举个例子：背包的最大重量是4。这些物品是：重量价值物品0115物品1320物品2430背包可以携带的物品的最大值是多少？以下解释和插图中出现的数字均基于此示例。二次元dp阵01背包还是一波五段解析。确定dp数组和下标的含义对于背包问题，有一种写法，就是用二维数组，即dp[i][j]表示取任意一个物品与下标[0-i]，放入容量为j的背包中，最大值是多少。光是看这个二维数组的定义，大家就会有些疑惑。看下图：永远记住这个dp数组的意思。下面的步骤都是根据这个dp数组的意思来的。如果你一头雾水，我们再回顾一下i代表什么，j代表什么。2、确定递归公式，复习dp[i][j]的含义：取任意下标为[0-i]的物品，放入容量为j的背包中，最大价值和为多少。那么有两个方向推出dp[i][j]，由dp[i-1][j]推出，即背包的容量为j，物品i的最大值为没有放在里面。此时dp[i][j]是由dp[i-1][j-weight[i]],dp[i-1][j-weight[i]引入的dp[i-1][j]]]是背包容量j-重量当[i]没有放物品i的最大值时，则dp[i-1][j-重量[i]]+value[i]（物品i的价值）是将物品i放入背包中获得的最大值。所以递归公式：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);3.如何初始化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(intj=bagWeight;j>=weight[0];j--){dp[0][j]=dp[0][j-weight[0]]+value[0];//i初始化为0时的情况}你应该搞清楚为什么这个初始化是逆序遍历？不能正向遍历吗？正向遍历确实是不可能的。dp[0][j]表示容量为j的背包在存放item0时的最大值，item0的值为15，因为题目说**Eachitemhasonlyone!**所以如果dp[0][j]不是初始值，应该是第0项的值，也就是15。但是一旦正序遍历，第0项就会被多次添加！例如代码如下：//For(intj=weight[0];j<=bagWeight;j++){dp[0][j]=dp[0][j-weight[0]]+value[0];}例如dp[0][1]为15，dp[0][2]=dp[0][2-1]+15;即dp[0][2]=30，则item0被重复放入。所以一定要向后遍历，保证item0只放入一次！这对于01背包来说非常重要。后面讲解滚动数组的时候，也会用到逆向遍历来保证item被使用一次！此时dp数组的初始化如下图所示：dp[0][j]和dp[i][0]都已经初始化了，那么还需要初始化多少个下标呢？dp[i][j]在求Number的时候一定是取最大值的那个，如果题目给的值都是正整数，那么所有非零下标都可以初始化为0，因为0是最小的值，不会影响取最大值的结果。如果题目给的值有负数，那么非零下标必须初始化为负无穷大。例如：某项的值为-2，但对应的位置还是初始化为0，那么取最大值时取0而不是-2，所以必须初始化为负无穷大。这样dp数组就可以在递归公式的时候取最大值，而不是被初始值覆盖。最终的初始化代码如下：//initializedpvector>dp(weight.size()+1,vector(bagWeight+1,0));for(intj=bagWeight;j>=weight[0];j--){dp[0][j]=dp[0][j-weight[0]]+value[0];}费了好大劲才把怎么初始化解释清楚，相信itornot很少有同学平时凭感觉初始化dp数组，但有时候感觉不靠谱。4.确定遍历顺序如下图所示，可以看出遍历有两个维度：物品重量和背包重量。那么问题来了，到底是先遍历物品还是先遍历背包的重量呢？容易明白。那我先给出代码先遍历物品，再遍历背包重量。//权重数组的大小为item个数for(inti=1;iweight={1,3,4};vectorvalue={15,20,30};intbagWeight=4;//二维数组vector>dp(weight.size()+1,vector(bagWeight+1,0));//初始化for(intj=bagWeight;j>=weight[0];j--){dp[0][j]=dp[0][j-weight[0]]+value[0];}//权重数组的大小为item的个数for(inti=1;i=0){dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);}}}这样打印出来的dp数据：空0实际上是不可用的。版本1可以打印出完整的dp数组，我就用版本1来说明。总结说了这么多，就把二次元dp的01背包说完了。在这里，其实可以发现，最简单的推导公式就是推导公式。推导公式估计看完就背下来了，难点在于如何初始化和遍历顺序。.可能有的同学没有注意到初始化和遍历顺序的重要性，等到后面我们尝试扣好背包面试题的时候大家就会感受到了。本文转载自微信公众号《代码随想录》，可通过以下二维码关注。转载本文请联系CodeCaprice公众号。