前言
相信不少读者看完标题会会心一笑，没错，今天我们要介绍的是 0-1 背包问题的解题思路。
谈动态规划（简称 dp），背包问题是绕不过去的话题，背包问题可以说是 dp 中的一种非常经典的问题了，掌握了背包问题， dp 才可以说是入门了，所以今天我们来看看背包问题怎么解，背包问题主要分为 0-1 背包，完全背包，多重背包，其中掌握 0-1 背包是基础，完全背包，多重背包其实是在 0-1 背包上的变形，所以我们今天主要谈谈 0-1 背包问题的解题技巧。
我们会分别用贪心， dp 两种方法来进行解题，另外我们之前在这篇文章里详细阐述了 dp 的解题技巧，其中提到了解 dp 解决的一种思路，先写出状态转移方程，其实 dp 还可以用另外的解题思路：状态转移表法。这篇文章我们会一起看看。
从介绍中就可以看到干货很多，建议先收藏再看，看完之后相信 0-1 背包不再是问题 ^_^
本文会从以下几点来讲解 0-1 背包问题
- 什么是 0-1 背包问题
- 只考虑重量的背包问题两种解法
- 贪心算法
- dp 解法
- 考虑物品重量及价值的 0-1 背包问题
什么是 0-1 背包问题
简单地说，就是有一组不同重量、不可分割的物品（每个物品有且仅有一个），每个物品都有其价值，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，求解背包中物品总价值最大值。
如图示：已知背包可承载 15 kg，怎么装其他物品，能使装入物品在满足装入背包总重量不超过 15 kg 的情况下装载的总价值最大。
如果考虑到物品价值确实比较复杂，那我们先不考虑价值，看看先只考虑重量该怎么解，即如何往背包里装物品，使在不超过背包最大可承载重量的情况下装入物品的总重量最大。
如果能求出最大可装载重量的解，再求最大价值的解相信应该有迹可寻。
接下来我们就用三种解法来试着求解 0-1 背包问题中背包可承载物品的最大重量和
贪心算法
以以上背包问题为例，背包最大承载量是 15 kg，物品重量分别为 12 kg，2 kg ，1 kg，1 kg，那么用贪心算法行不行呢，试试看，贪心算法的每一步都是求问题的最优解，所以第一次选 12 kg 的物品，第二次 取 2 kg，第 3 次取 1 kg，刚好达到了背包的最大承载量 15 kg，所以这么看来用贪心算法可以解咯？我们在 上文学到贪心算法时提到如果一个问题用贪心算法得出的解是全局最优解，一定要警惕！是否只是相关的条件恰好满足贪心算法得出的解而已，如果我换个条件呢，比如我现在换成背包的最大承载量是 10 kg，物品的重量分别为 7 kg， 5 kg，4 kg，如果用贪心算法的话，第一次选 7 kg，接下来 5 kg，4 kg 都不能选了，于是用贪心算法得出的解是 7 kg，但实际上很明显应该选 5 kg，4 kg，也就是说最大重量是 9 kg。所以说贪心算法不可行
dp
接下来开始我们的重头戏，来看看如何用 dp 来求解 0-1 背包问题。
套用 dp 解题四步曲来求解，步骤如下：
1、判断是否可用递归来解
顾名思义， 0-1 背包问题中的 0-1 指的是每个物品要么选，要么不选，选的话用 1 表示，不选的话用 0 表示，这显然就是个组合嘛，把所有组合都穷举出来再求出最大重量不就完了。既然是组合问题，那显然可以用递归求解（排列组合怎么解，强烈看下这篇文章）,没看过也没关系，我会一步步来带大家看看如何用递归来解（强烈建议看下这篇递归解题的文章，本号成名作，好评如潮！）。
假设背包的最大承载重量是 9。有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。物品编号从 0 到 4。
我们定义 f(i, w) 为将要决策第 i 个物品是否放入背包时背包当前的总重量为 w，比如 f(1, 2) 即代表将要决策第 2（物品编号从 0 开始，所以是决策第 2 个物品） 个物品是否放入背包，决策前背包物品的总重量为 2。
则不难得出递推公式如下
什么时候终止呢，显然是没有物品可选或者背包中选择的物品总重量超过了背包可承载的重量时。
有递推公式也有终止条件，显然符合递归的条件，于是我们写下了如下递归代码、
public class Solution { // 最终的解：即背包可放入的最大重量 private static int maxw = Integer.MIN_VALUE; // 每个物品的重量 private static int[] weights = {2,2,4,6,3}; // 背包能承载的最大重量 private static final int knapsackWeigth = 9; private static void knapsack(int i, int w) { // 物品有多少个 int weightSize = weights.length; // 物品选完或者背包里选的物品总重量超过了背包可承载的总重量，递归结束 if (i > weightSize-1 || w >= knapsackWeigth) { if (w <= knapsackWeigth) { maxw = Math.max(maxw, w); } return; } // 第 i 个物品不选 knapsack(i + 1, w); if (w + weights[i] <= knapsackWeigth) { // 选了第 i 个物品 knapsack(i + 1, w + weights[i]); } } public static void main(String[] args) { knapsack(0, 0); System.out.println("maxw = " + maxw); } } 复制代码
时间复杂度是多少呢，每个物品要么选要么不选，两种状态，如果有 n 个物品，时间复杂度显然是 O(2n)，指数级，不可接受！
2、分析在递归的过程中是否存在大量的重复子问题（ dp 第二步）
怎么分析是否有重复子问题，看不出来可以画出递归树，通过分析不难得出从 f(0,0) 开始的递归树如下
图中可以看出存在重叠子问题，f(2,2) 与 f(3,4) 重复
3、采用备忘录的方式来存子问题的解以避免大量的重复计算（剪枝）
既然存在大量重复子问题，我们就把这些子问题缓存住，避免重复计算，代码如下
// 备忘录，缓存子问题 private static HashMap mem = new HashMap<String, Integer>(); private static void knapsack(int i, int w) { // 物品有多少个 int weightSize = weights.length; // 物品选完或者背包里选的物品总重量超过了背包可承载的总重量，递归结束 if (i > weightSize-1 || w >= knapsackWeigth) { if (w <= knapsackWeigth) { maxw = Math.max(maxw, w); } return; } String key = i + "," + w; // 有 value，说明子问题之前已经解过了，无需再计算! if (mem.get(key) != null) { return; } mem.put(key, 1); // 第 i 个物品不选 knapsack(i + 1, w); if (w + weights[i] <= knapsackWeigth) { // 选了第 i 个物品 knapsack(i + 1, w + weights[i]); } } 复制代码
缓存之后就做了大量减枝的操作，时间复杂度自然急剧下降
4、改用自底向上的方式来递推，即 dp 解法
既然满足使用 dp 的条件 (递归+重叠子问题)，那我们来看看如何用 dp 来解，在我们之前的一文学会 dp 解题技巧 文章中，我们求解 dp 时都是要列出状态转移方程，但在 0-1 背包问题中，如果用 dp 方程不好表示，所以我们可以看看动态规划的另一种也是比较常用的解法：状态转移表法。
我们知道，动态规划其实是把问题分解成了多个阶段（或者说多个子问题），每个阶段的解其实是由上个阶段的解推导而来，所以我们只要把每个阶段的所有解都保存下来，自然而然能推导到下一阶段的所有解，这样层层推导，求出最后一个阶段的所有解之后，从最后一个阶段的解中即可以得出全局的最优解，在保存每个阶段所有解的过程中，其实我们也合并了重复解，这样也就避免了问题规模的指数增长。
如图示：在第二阶段解的过程中，有两个 f(2，2)，我们在保存的过程中，其实是把这两个重复的解给合并成一个解了，避免了问题规模的指数增长！
现在问题来了，怎么表示每个阶段的解呢，从以上递归树的推导中，我们不难发现应该是个二维数组（f(i, w) 有两个变量，所以是个二维数组）。我们定义这个二维数组为 state[i][w], 代表第 i 个阶段所能达到的所有状态（从 0 到背包能承载的重量）。
同样，假设背包的最大承载重量是 9。有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。**物品编号从 0 到 4 ** 举个例子，对于第 0 个（物品编号从 0 开始）物品（重量为 2）来说，它要么选，要么不选，选了的话背包中物品的总重量为 2，不选的话则为 0 ，于是我们有 state[0][0] = true, state[0][2] = true 这两种状态，填入状态转移表如下
第 1 个物品的重量为 2，它也是要么选，要么不选，如果选了的话总重量为 2 （第一个物品不选） 或 4（第一个物品选了），不选的话总重量为 0（第一个物品不选） 或 2（第一个物品选了）。 于是我们可知 state[1][0] = true, state[1][2] = true, state[1][4] = true, 填入状态转移表如下图所示
依此类推不断地决策后可以把每个阶段的解都填满，整个阶段的状态转移表如下
最大重量和怎么看呢，在最后一个阶段决策后（最后一行），从右往左数第一个值为 true 对应的重量，比如以上图为例，最后一个阶段决策后，从右往左数第一个值为 true 的状态对应的重量为 9，所以此背包问题的最大重量和即为 9。
思路有了，看下代码如何实现的
/** * * @param weights 各个物品的重量 * @param knapsackWeight 背包可承受的最大重量 * @return */ public int knapsack(int[] weights, int knapsackWeight) { int n = weights.length; // 物品个数 boolean[][] states = new boolean[n][knapsackWeight+1]; // 第一个物品不选 states[0][0] = true; if (weights[0] <= knapsackWeight) { // 第一个物品选了 states[0][weights[0]] = true; } for (int i = 1; i < n; i++) { for (int j = 0; j < knapsackWeight + 1; j++) { // 第 i 个物品不放入背包中 if (states[i-1][j] == true) { states[i][j] = states[i-1][j]; } } for (int j = 0; j <= knapsackWeight-weights[i]; ++j) { //把第i个物品放入背包 if (states[i-1][j]==true) { states[i][j+weights[i]] = true; } } } // 最后一个阶段决策后，从最后一行右到左取第一个值为 true 对应的重量，即为所求解 for (int j = knapsackWeight; j >= 0; j--) { if (states[n-1][j]) { return j; } } return 0; } 复制代码
时间复杂度是多少？两重循环，显然是 O(n2)，空间复杂度呢，states 是个二维数组，所以也是 O(n2)，空间复杂度能否优化，在以上的推导过程中，其实我们知道，当前阶段的解，只与上一个阶段的解有关，与上上个阶段的解无关，也就是动态规划的一个性质：无后效性，即当前阶段只要知道上个阶段的解即可，不关心上个阶段的解是怎么得来的。以我们的状态转移表为例
第五阶段的解其实只与第四阶段的解有关，与前面几个阶段的解无关，也就是说其实我们只用一个一维数组保存每个阶段的解即可，这样空间复杂度就从 O(n2) 变成了 O(n),来看看用一维数组怎么做
/** * 使用一维数组来保存每个阶段的解 * @param weights 每个物品的重量 * @param knapsackWeight 背包可承受的最大重量 * @return */ public static int knapsack2(int[] weights, int knapsackWeight) { int n = weights.length; // 物品个数 boolean[] states = new boolean[knapsackWeight+1]; // 第一个物品不选 states[0] = true; if (weights[0] <= knapsackWeight) { // 第一个物品选了 states[weights[0]] = true; } for (int i = 1; i < n; i++) { for (int j = knapsackWeight - weights[i]; j >= 0; --j) { //把第i个物品放入背包 if (states[j]) { states[j + weights[i]] = true; } } } // 最后一个阶段决策后，从最后一行右到左取第一个值为 true 对应的重量 for (int j = knapsackWeight; j >= 0; j--) { if (states[j]) { return j; } } return 0; } 复制代码
注意下面红框的 代码：
j 必须从后往前遍历，而不能从 0 开始遍历，如果从 0 开始遍历，states 前面 index 的值会影响到后面值的计算，如果不理解，可以自己动手试试，打下断点调试一下。
考虑物品重量及价值的 0-1 背包问题
之前我们只考虑了物品重量的 0-1 背包问题，接下来我们考虑一下如果考虑物品价值情况，怎么在满足背包最大承载重量的情况下求物品的最大价值的解。
先考虑用递归求解，之前我们是用 f(i, w) 表示选择物品 i 前的重量为 w，现在既然考虑价值，那我们再加个价值变量不就完了，于是我们定义 f(i, w, v) 为选择物品 i 前装入背包的总重量为 w，总价值为 v，代码如下，改动其实很小
// 最终的解：即背包可放入的最大重量 private static int cv = Integer.MIN_VALUE; // 每个物品的重量 private static int[] weights = {2,2,4,6,3}; // 每个物品的价值 private static int[] values = {3,4,8,9,6}; // 背包能承载的最大重量 private static final int knapsackWeigth = 9; private static void knapsack(int i, int w, int v) { // 物品有多少个 int weightSize = weights.length; // 物品选完或者背包里选的物品总质量超过了背包可承载的总重量，递归结束 if (i > weightSize-1 || w >= knapsackWeigth) { if (w <= knapsackWeigth) { cv = Math.max(cv, v); } return; } // 第 i 个物品不选 knapsack(i + 1, w, v); if (w + weights[i] <= knapsackWeigth) { // 选了第 i 个物品 knapsack(i + 1, w + weights[i], v + values[i]); } } 复制代码
以 f(0,0,0) 为根节点画出递归树如下
可以看到 f(2,2,4) 与 f(2,2,3) 这两个相当于重复子问题，因为这两者的 i 与 w 是一样的，而 4 的价值显然比 3 高，所以应该选 f(2,2,4)。 同理，对于 f(3,4,8) 和 f(3,4,7) 来说,显然应该选 f(3,4,8), 但需要注意的是虽然这两对相当于重复子问题，但却没法用备忘录的形式来解，对于 f(i, w, v) 这个函数来说，如果用备忘录模式，缓存的 key 是由 i, w, v 这三个变量决定的，i，w，v 相同，key 就相同，这样缓存才有意义，而由以上的递归树可知，i，w，v 三者没有完全相同的，用备忘录模式也就失去了意义，所以针对这种无法用备忘录但却存在重复子问题的题型要特别注意要特别注意！
接下来我们考虑用动态规划怎么做 首先我们还是定义二维数组 states[i][w+1] 为每一层所能达到的状态,不过此时它存的不是再是 true 了，而是存了当前状态背包物品里最大的总价值。
/** * * @param weights 各个物品的重量 * @param weights 各个物品的价值 * @param knapsackWeight 背包可承受的最大质量 * @return */ public static int knapsack(int[] weights, int values[], int knapsackWeight) { int n = weights.length; // 物品个数 int[][] states = new int[n][knapsackWeight+1]; for (int i = 0; i < n; i++) { for (int j = 0; j < knapsackWeight+1; j++) { states[i][j] = -1; } } // 第一个物品不选 states[0][0] = 0; if (weights[0] <= knapsackWeight) { // 第一个物品选了 states[0][weights[0]] = values[0]; } for (int i = 1; i < n; i++) { for (int j = 0; j < knapsackWeight + 1; j++) { // 第 i 个物品不放入背包中 if (states[i-1][j] > 0) { states[i][j] = states[i-1][j]; } } for (int j = 0; j <= knapsackWeight-weights[i]; ++j) { //把第i个物品放入背包 if (states[i-1][j] >= 0) { states[i][j+weights[i]] = Math.max(states[i-1][j] + values[i], states[i][j+weights[i]]); } } } // 求出总价值的最大值 int max = Integer.MIN_VALUE; for (int j = knapsackWeight; j >= 0; j--) { max = Math.max(max, states[n-1][j]); } return max; } 复制代码
时间和空间复杂度都是 O(n2)，同理，我们可以对空间复杂度进行优化，我们把二维数组改用一维数组表示，即 states[i][w+1] 改为 states[w+1]，代码如下
/** * 使用一维数组来保存每个阶段的解 * @param weights 各个物品的重量 * @param weights 各个物品的价值 * @param knapsackWeight 背包可承受的最大质量 * @return */ public static int knapsack2(int[] weights, int values[], int knapsackWeight) { int n = weights.length; // 物品个数 // 改用一维数组来保存每个阶段的状态，减少空间复杂度 int[] states = new int[knapsackWeight+1]; for (int j = 0; j < knapsackWeight+1; j++) { states[j] = -1; } // 第一个物品不选 states[0] = 0; if (weights[0] <= knapsackWeight) { // 第一个物品选了 states[weights[0]] = values[0]; } for (int i = 1; i < n; i++) { for (int j = knapsackWeight-weights[i]; j >= 0; --j) { //把第i个物品放入背包 if (states[j] >= 0) { states[j+weights[i]] = Math.max(states[j] + values[i], states[j+weights[i]]); } } } // 所有阶段结束后求出 states 中的最大解 int max = Integer.MIN_VALUE; for (int j = knapsackWeight; j >= 0; j--) { max = Math.max(max, states[j]); } return max; } 复制代码
总结
本文详细剖析了 0-1 背包问题的解法，先从只考虑重量的解，再逐步过滤到考虑价值的 0-1 背包问题，由浅入深，相信大家掌握了只考虑重量的 0-1 背包问题的求解，再考虑背包价值问题的话问题不大。这也提醒我们，求解复杂的难题，一开始变量比较多可能不好考虑，可以先把变量去掉看看是否有解题思路，解完之后再加变量求解也许会更简单一些。
文中所有代码已更新到我的 github 地址（github.com/allentofigh…
参考
极客时间 初识动态规划：如何巧妙解决“双十一”购物时的凑单问题？ time.geekbang.org/column/arti…
