今天是动态规划的第三天！来到了万众瞩目的 背包问题！

首先，什么是背包问题？简单来说就是有一个背包，容量已知，然后有几个物品，已知物品的重量与价值，求如何放物品使得背包内物品的价值最高。根据物品的数量可以把背包问题细分为01背包和完全背包等更细的分类：

背包问题分类

鉴于01背包是各类背包问题的核心基础，因此本篇优先探索01背包问题的核心解法及其内在逻辑。

01背包🎒问题概述：有n件物品和一个最多能装w重量的背包。第i件物品的重量为weight[i]、价值为value[i]。每件物品最多只能用一次。求解将那些物品装入背包里 可使得背包总价值最大？

01背包问题

看到问题，首先我们得想到的是 这个问题的暴力解法应该是如何？这点其实不难想，对于每个物品，其实就是选与不选两种情况，因此我们可以用回溯法搜索出所有的情况，对于n个物品而言，时间复杂度是O(2 ^ n)。所以暴力解法不是做不出来，而是他是指数级别的复杂度，所以需要动态规划来优化。

下面以一个例子来讲解：
背包重量为4，
物品0 重量1 价值15
物品1 重量3 价值20
物品2 重量4 价值30
求背包的最大价值。

解法是 二维dp数组解法：
还是用动态规划五部曲来分析一下：

1. 在分析二维数组的含义之前，我们现探究一下为什么要使用二维数组---因为我们有两个维度需要表示---物品 和 背包容量。如图所示，二维数组为dp[i][j]:

   
   
   二维数组dp[i][j]
   
   

   由图可知，我们使用i表示物品，j表示背包容量/背包重量。（当然这只是习惯问题，你也可以用j来表示物品）。根据动态规划 是 通过子问题的求解推导出整体的最优解 的思路，我们可以一步步尝试填写一下表格：例如把物品0放入背包：

   
   
   物品0放入背包
   
   因为物品0只有一个，所以最多就只能放一次，这是为什么当容量>=2之后，总价值依然是15的原因。接下来尝试把物品1放入背包：
   
   物品1放入背包
   
   

   背包容量为3时，可选择放物品0或物品1，显然放物品1的价值更高，所以选择放物品1或取更高的价值20.
   背包容量为4时，上一行状态不变，背包只能放物品0；这一行除了物品0之外还有物品1可以选，而且可以两者都放得下，所以最高价值为35.

由以上例子的分析，我们不难发现dp数组的含义：dp[i][j]表示在[0-i]的物品里任意选择，放进容量为j的背包，所产生的最大价值。举例说明：在上图中dp[1][4]表示在物品0和物品1里任意选择，使得放入容量为4的背包时 产生的最大价值。

2. 递推公式
   这一步就是要确定dp[i][j]可由哪些方向推到而来。还是用dp[1][4]举例，对于物品1而已有两种情况：1️⃣把物品1放入背包 2️⃣不把物品1放入背包
   如果不把物品1放入背包，那么背包的价值应该是dp[0][4]，即容量为4时，只考虑是否放物品0 的最大价值：

   
   
   不放物品1时背包价值的推导方向

如果把物品1放入背包，那么价值应该是物品1的价值 加上 背包剩余容量时考虑是否放入物品0的价值。带入数值就是 背包剩余容量1时，是否放入物品0的价值dp[0][1]:

放入物品1时背包价值的推导方向

因此，我们只需将两种方式取最大值 即可 求的 放与不放物品1的最大值：
dp[1][4] = max(dp[0][4], dp[0][1] + value[1])
将以上公式抽象化可以得到 不放物品i的价值为 dp[i-1][j]；放物品i的价值为dp[i-1][j-weight[i]] + value[i]

综上所述，递推公式为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

3. dp数组的初始化
   关于初始化，不是瞎猫碰上死耗子，胡乱一猜。一定要与定义吻合。
   从dp[i][j]的定义出发，当背包容量为0时，无论物品有哪些，价值都是为0：

   
   
   背包容量为0时的初始化
   
   

   由递推公式可知 i 都是由 i-1 推导而来，也就是图中的下一层都是由上一层的某一个推导而来，因此第一行的数据，即i=0时，就一定要初始化。对此也不难，当容量不足以放物品0时，价值也就不存在；当重量足够放物品0时，价值一直时物品0的价值。

   
   
   dp数组第一行初始化
   
   至于其他部分，鉴于在后续遍历中都会被覆盖，因此是多少都无所谓，所以为了方便我们就都初始化为0就好了。
   
   完整的dp数组初始化

4. 确定遍历顺序。
   从图中可以看出，遍历有两个维度：物品 和 背包重量。至于两个维度先遍历哪个，我们得理解递推方向的本质。
   根据递推公式 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][j]的左上部分（包括正上方），所以只需保证在求得dp[i][j]之前，左上部分（包括正上方）是有值的就可以了。接下来我们看看两种遍历顺序能否保证dp[i][j]左上方有值。
   1️⃣先遍历物品后遍历背包容量

   
   
   先遍历物品
   
   

   可以看到，遍历顺序是，从左到右，然后一行一行向下遍历（图中蓝色箭头）那在遍历到红框时，他的左上部分时已经有值了的，所以这种遍历方式可行。
   2️⃣先遍历背包容量后遍历物品

   
   
   先遍历背包容量
   
   遍历顺序是从上到下遍历，然后一列一列向右进行（图中蓝色箭头，顺序是从左往右）。因此在遍历到红色方框的时候，左上角也是已经有值了，因此这种方式也可行。
   所以虽然两种方式的遍历顺序不同，但是都满足dp[i][j]需要的数据就是左上角这一需求，所以都可以。

5. 举例推导dp数组 （打印结果）

   
   
   dp数组结果
   
   

   本例最终结果就如上图所示。然后本题在LeetCode没有原题，所以暂时不出具体题目。本篇旨在分析清楚01背包问题的基本底层逻辑，希望给背包问题打好基础。背包问题只是基础，在LeetCode中需要掌握一些实际应用。

（稍后补充例题讲解） - - - - -