一般来说，只要掌握了基本的 01背包问题 和 完全背包问题 就足够应付大多数面试。二者作为背包问题，区别就是对于物体的数量限制。

01 背包 和 完全背包 的区别

01背包中不同物体只有一个，也就是说对于任一物体，只有选或不选两种选择，而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。

01 背包

有 N 件物品和一个最多能背重量为 W 的背包。第i件物品的重量是 weight[i]，得到的价值是 value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
要素包括：

• N 件物品
• 容量为 W
• 重量列表 weight
• 价值列表 value
• 以及解决问题的前提：每件物品只能用一次，这也是 01 背包的关键特征

每个物品只能选或者不选，所以暴力解法的时间复杂度是 $O(2^n)$，指数级别。
所以需要动态规划来优化。

我们分别分析之前动态规划专题中提到动态规划的要素：

1. 找到合适的记录方式（确定dp数组以及下标的含义）
   典型的01背包，我们可以使用一个二维数组 $dp[i][j]$ 来表示到第 $i$ 个物品时容量为 $j$ 时背包的最大的价值。

2. 找到状态转换方程
   根据记录方式,可以得到:

   $$dp[i][j] = max\{dp[i-1][j-weight[i]]+value[i], dp[i-1][j]\}$$

   （这都得好好体会）

3. 初始化
   根据记录方式，在 $j=0$ 时，背包的容量为 0，放不下任何物品，价值始终为 0，所以将 $dp[i][0]$ 赋值为 0。
   注意：常见的求最优解的背包问题中，有两种不太相同的问法。一种要求“恰好装满背包”时的最优解，一种则没有要求必须把背包装满。一种区别这两种问法的实现方法就是在初始化的时候有所不同。
   如果要求恰好装满背包，那么在初始化时除了 $dp[0][0]$ 为 0，其它 $dp[0][1..V]$ 均设为 $-\infty$，这样就可以保证最终得到的 $dp[M][N]$ 是一种恰好装满背包的最优解。
   如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 $dp[0][0..V]$ 全部设为0。
   可以这样理解： $j=0$ 时初始化的数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的 nothing “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是 $-\infty$ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。

4. 找到运算顺序
   状态转换方程中都是通过当前的 $i,j$ 之前的结果得到的，所以 $i,j$ 都应该从小到大。

之后便可以通过分析的结果运算01背包问题。

完全背包

上面说到完全背包的物品数量是无限的，也就是说，有 N 种物品，每种物品有无限多个可以任取。
初始状态01背包和完全背包一致，当 i > 0 时 dp[i][j] 也有两种情况：

1. 不装入第i种物品，即dp[i−1][j]，同01背包；
2. 装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品。 所以状态转换方程就是

这个状态转移方程与01背包问题唯一不同就是max第一项不是dp[i-1]而是dp[i]。