注意：我们已经在Github 上编译了所有指南来解决您的问题：https://github.com/youngyangyang04/leetcode-master，以便任何人都可以在自己的计算机上阅读。该仓库每天更新。请支持我们，给我们一颗星。那！

从本周开始，我们将正式开始讲解背包问题！

关于背包问题的经典资源当然是《9 Lectures on Backpacks》。如果您在公众号“Code Caprice”后台回复，可以获得Backpack 9课程的PDF。

但说实话，9个背包旅行课程对于初学者来说不太友好。都是伪代码，有点复杂，难以理解。

其实对于面试来说，掌握01背包和完整背包就足够了。 您最多还可以获得多件装。

如果你不知道这几种背包的区别，可以在这里画个图，如下所示：

至于背包课程9中的其他背包，都属于竞技水平，所以面试时很少被问到。题库还显示了01 个背包和完整背包，因为leitcode 甚至没有询问多个背包。足够的。

完整的背包也是01背包的稍微修改版。这意味着一个完整背包中的物品数量是无限的。

所以背包问题最重要的理论基础就是01背包，一定要吃透。

Leetcode上没有纯粹的01背包题。都是01背包应用题。所以需要转换为01背包问题。

因此，我们首先通过一个纯粹的01背包问题来解释一下01背包的原理。后面我们讨论leetcode问题的时候，重点会放在如何转化为01背包问题。

有些录音朋友以前可能能把背包写得很好，但如果你仔细阅读这篇文章，我想你会得到一些意想不到的结果。

01 背包

有一个背包，可以装N件物品，最大重量为W。令第i项的权重为weight[i]，得到的值为value[i]。每个物品只能使用一次。找出哪些物品为您的背包增加了最大的总价值。

这是一个标准的背包问题，所以很多同学看到这里自然会想到背包，但却不知道如何硬解。

其实这不是自下而上的思考，而是习惯性地思考背包。那么暴力解决方案应该是什么呢？

由于每个项目实际上只有两种状态：已检索或未检索，因此我们可以使用回溯技术来查找所有情况。在这种情况下，时间复杂度为O(2^n)，其中n 表示项目数。

因此，暴力破解的时间复杂度是指数级的。在这种情况下，优化需要动态规划解决方案。

下面的讨论提供了一个例子。

背包的最大重量为4。

这些项目是：

重量值商品0115 商品1320 商品2430

背包中可以放置的物品的最大价值是多少？

以下描述和附图中出现的所有数字均基于该示例。

二维dp数组01背包

仍在分析第5 部分规则。

判断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] by dp[i – 1][j -weight[i]] 已经被引入，dp[i – 1][j -weight[i]]是背包容量为1时的物品。是i 的最大值。 j – 重量[i]，dp[ i – 1][j – 重量[i]] + value[i]（物品i的值）是物品i放入背包时获得的最大值。公式：dp[i][j]=max(dp[i – 1][j], dp[i – 1][j – 权重[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-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]表示存放物品0时j的最大背包容量。该问题表示每项只有一个，因此第0 项的值为15。 **所以如果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，则将重复第0 项。到。

所以如果你想让item 0只插入一次，就需要向后遍历。这对于01背包来说非常重要。后面我们讨论滚动数组的时候，也会使用闪回遍历来保证某个item已经被使用过一次。

此时dp数组的初始化状态将如下图所示。

dp[0][j]和dp[i][0]已经初始化了，那么其他下标应该初始化到什么程度呢？

在求dp[i][j]时，我们需要取最大的数。如果问题中指定的值都是正整数，那么所有非零下标都可以初始化为0，因为所有0都是0。这是最小值，没有影响。获得最大结果。

如果问题中指定的值为负数，则非零下标必须初始化为负无穷大。例如某一项的值为-2，但对应的位置仍然初始化为0。一旦取最大值，它将是0而不是-2，因此必须将其初始化为负无穷大。

这样，dp 数组就可以取其最大值，而不是在递归过程中被初始值覆盖。

最终的初始化代码为：

//初始化dpvectorvectorintdp(weight.size()+1,vectorint(bagWeight+1,0));for(intj=bagWeight;j=weight[0];j–){dp[0][j]=dp [0][j-weight[0]]+value[0];} 我很难清楚地解释如何初始化dp数组，但是很多学生通常基于情感来初始化dp数组，我认为它会改变。但在某些情况下可能会有这种感觉。不受信任。

确定遍历顺序。如下图所示，可以看到有两个遍历维度：物品和背包重量。

那么问题来了，我应该先检查物品还是先检查背包的重量呢？

事实上，这是可以做到的！但是，如果您先查看这些项目，会更容易理解。

然后首先给它一些代码，首先扫描物品，然后扫描背包的重量。

//权重数组的大小为物品数量for(inti=1;iweight.size();i++){//遍历物品for(intj=0;j=bagWeight;j++){//背包capacity of if(jweight [i])dp[i][j]=dp[i-1][j];//这个是显示dp数组元素的变化elsedp[i][j ]=max(dp[i-1] [j],dp[i-1][j-weight[i]]+value[i]);}} 先过背包，再过物品也是可以的。 （注意这里使用的二维dp数组）

例如：

//权重数组的大小为物品数量for(intj=0;j=bagWeight;j++){//遍历背包容量for(inti=1;iweight.size();i++){//遍历项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]);}}为什么这是可能的？

理解递归的本质和递归的方向。

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 数组并将其与你拥有的进行比较。如果你猜，问题很快就会被发现。

我知道很多朋友都面临着近2000个问题，却很难上手。我花了半年时间编辑github学习项目的leetcode指南（https://github.com/youngyangyang04/leetcode-master）。这包括详细信息以及经典问题。它们按顺序排列，并且在视频中也解释了它们的解决方案。这绝对值得一颗星。

完整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] ;}//权重数组的大小为项目数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 并未实际使用。版本1可以打印完整的dp数组。版本1 将用于讨论。

总结

我已经谈了很多了，但是我已经解释完2D DP 01背包了。其实最简单的就是推导公式。我想你读完之后就能记住推导公式了。棘手的部分是初始化和遍历顺序。

有些同学可能没有意识到初始化和遍历顺序的重要性，但是后来你问他们背包面试问题的时候大家就会意识到了。

下次我会分析1D DP数组和2D实现的01 Backpack（滚动数组）的区别，并讲一下初始化和扫描顺序的区别，敬请期待！

我是卡尔，一名程序员。我的个人主页是https://github.com/youngyangyang04。

这里8:35每天准时问经典算法题。我选择的每一个问题都不是独立的，而是由浅入深地相互联系，来整理你的算法知识，让你轻松学习算法。

@代码随想录期待您的关注

我们花了六个月的时间制作了Likou的刷题指南。本指南发布在Github 上。点击下面的链接即可查看。