背包问题是动态规划问题中的经典问题，也是 OJ 题目中的常客，而 01 背包问题则是最简单的背包问题。

问题概述

01 背包问题可以使用通用的形式描述为有一个容量为 V（V > 0） 的背包，向其中放入物品，且每个物品的体积和重量各不相同。假设有 n 个物品待选，其占用体积分别为 C1, C2 … Cn，重量分别为 W1, W2 … Wn。总有方案使得放入物品的总重量最大，求最大总重量是多少。

解题思路

贪心

看少去好像可以使用贪心算法，但是仔细考虑就能发现，最后结果未必正确。 举个简单的反例：假设背包容量为 5，有 3 个物品待放入，其体积分别为 1、2、3，重量分别为 6、10、12。如果使用贪心算法，则最后结果是 16，但是很明显结果应该为 22。 毕竟，01 背包问题中物品不可分割，导致使用贪心算法求得的解会有背包无法装满的情况发生，此时放入物品的重量和体积的比值会比贪心算法预估情况小。 因为，贪心算法总是考虑当前最优，而不从整体考虑，一旦所有的贪心得出的最优解无法还原合法的总体情况，就会导致解题失败。 所以，01 背包问题不要使用贪心算法。

搜索

可以考虑将每个物品的信息做成树的节点，然后根节点是一个重量为 0 且体积耗费也为 0 的节点元素，要放入背包的物品就是它的子节点，不断放入新物品就意味着不断对当前路径加上新的子节点。那么最后要求的问题就是找到一条路径，保证它的所有节点的体积和不大于 V 且重量和最大。 显然，深度搜索可以解决这个问题。但是，深度搜索的弊端就是要搜索所有的可能的排列方案，算法的时间复杂度大概是 O(n!)，如果题目输入规模较大，那么深度搜索就要进行多次计算。比如：对于编号 1、2 … n 的物品，其中如果有体积不大于 V 的方案为 1、2、3，则深度搜索一定还要搜索判断 2、3、1 和 3、2、1 等其他等价的方案，会进行大量重复计算。 所以，问题规模较大时不宜使用深度搜索算法解决背包问题。

动态规划

贪心算法不能求得完美答案的时候，总是可以使用动态规划方法来试一试。而动态规划方法最重要的步骤就是构建状态转移方程，或者说是找出递推方案。 对于本题来讲，可以如此推到：假设已知编号从 1 到 i-1 的物品的放入方案，接着考察要放入的下一个物品编号为 i，要使得新方案的重量最大。判断的方法很简单，就是看一下剩余空间体积是否不小于这个物品的体积 Ci，如果能放下这个物品，那么之前的方案必定也能够放入容积为 V-Ci 的背包中，反之则不能。 这样，对于以上的递推方案采用编程模型表示为： 使用二维数组 int[][] dp = new int[n + 1][V + 1] 缓存计算结果，这个二维数组中单个元素 dp[i][j] 代表对编号 1 到 i 的物品放入容积为 j 的背包，放入物品的最大可能重量。那么可以写出状态转移方程：

1
2

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Ci] + Wi)
其中 Ci 表示编号为 i 的物品的体积，Wi 表示其重量

为了方便计算，i 或 j 为 0 时二维数组元素 dp[i][j] 值为 0。 这样，横坐标从 1 开始一直到 n，对应纵坐标则是从 Ci 开始一直到 V，不断计算二维数组元素的值，最后的 dp[n][V] 就是本题的所求结果。写成伪代码就是：

1
2
3

for i = 1 .. n
    for j = Ci .. V
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - Ci] + Wi)

算法优化

基本空间复杂度优化

本题动态规划解法的算法空间复杂度为 O(n * V)，数据规模较大的时候算法会占用极大的空间，可以考虑能否不使用二维数组缓存中间运算结果。

观察状态转移方程可以直到实际数组第 i 行元素大小只和第 i - 1 行的两个元素内容有关，而且一旦 i 行中待求元素的编号确定，则 i - 1 行两个相应元素的编号也就随之确定了。所以，可以考虑只使用一维数组缓存原先二维数组的每一行的运算结果，在新的结果计算出来后覆盖一维数组的内容以便下一轮计算，即缓存数组为 int[] dp = new dp[V + 1]。 相应的状态转移方程就变化为：

1

dp[j] = max(dp[j], dp[j - Ci] + Wi)

其中，右边的 dp[j] 和 dp[j - Ci] 表示上一轮计算中的相应容量的最大放入重量。

最后，一定要注意算法伪代码会变成：

1
2
3

for i = 1 .. n
    for j = V .. Ci
        dp[j] = max(dp[j], dp[j - Ci] + Wi)

第二层循环必须从 V 到 Ci，保证每次调用的 dp[j] 都是上一轮计算的结果；如果是从 Ci 到 V 则 dp[j -Ci] 就会变成本轮计算中的相应容量的最大放入重量。

那么，最终可以得到算法伪代码：

1
2
3
4
5
6
7
8

void zeroOnePack(cost, weight)
    for i = V .. cost
        dp[i] = max(dp[i], dp[i - cost] + weight)

int calculate(n, V)
    for i = 1 .. n
        zeroOnePack(Ci, Wi)
    return dp[V]

可选的时间复杂度优化

空间优化后所求的结果就是 dp[V]，而要求它的值就要直到上一轮计算的 dp[V] 和 dp[V - Cn] 的值，而要求 dp[V - Cn] 的值还要知道上一轮的 dp[V - Cn] 和 dp[V - Cn - Cn-1] 的值。这样不断递推就可以知道，第一轮计算结果中最小的编号只要是 V - (C1 + C2 + … + Cn) 与 C1 中更大的值就可以了，且每一轮的要记录的缓存结果的最小编号也是 V - (Ci + Ci+1 + … + Cn) 与 Ci 间的最大值。所以算法伪代码可以优化为：

1
2
3
4

void zeroOnePack(cost, weight)
    bound = max(V - sum(Ci ... Cn), Ci)
    for i = V .. bound
        dp[i] = max(dp[i], dp[i - bound] + weight)

这个优化步骤对于 V 较大的情况有很大的帮助，但如果 V 较小时因为会进行多余的求和运算和比较运算，所以反而可能会拖慢程序运行速度。

初始化调整

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目 要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。对两种不同类型背包问题的求解方法可以使用不同的初始化方案来解决。

如果是要求恰好装满背包，那么在初始化时除了 dp[0] 为 0 ，其它 dp[1 .. V] 均设为 −∞ ，这样就可以保证最终得到的 dp[V] 是一种恰好装满背包的最优解。 如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 dp[0 .. V] 全部设为 0 。

这是因为：初始化的数组 dp 事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可以在什么也不装且价值为 0 的情况下被“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，应该被赋值为 -∞ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0 ，所以初始时状态的值也就全部为 0 了。 这个初始化方法也适用于其他更复杂的背包问题。

当然，应该注意在实际编程过程中要谨慎处理 -∞ 和常数的加法问题。对于恰好装满型的背包问题，应该有伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

dp[0] = 0
for i = 1 .. V
    dp[i] = -1

void zeroOnePack(cost, weight)
    for i = V .. cost
        temp = dp[i - cost] + weight
        if (dp[i - cost] == -1)
            temp = -1
        dp[i] = max(dp[i], temp)

如果单纯将 dp[1 .. V] 赋值一个负常数用来表示 -∞，但不做其他处理，则无法模拟 -∞ 和常数相加结果仍为 -∞。因为 weight 的数值极有可能很大，或者数组元素每轮计算不断加上不同的 weight 导致结果变成非负数。 这样，最后如果 dp[V] 为 -1 则表示问题无解，否则则 dp[V] 为恰好装满背包的最大重量。

参考

背包问题九讲