01背包问题

商店的货架上摆放着不同重量和价值的商品，一个小偷在商店行窃，他携带的背包只能装固定重量的商品。装哪些商品才能获得最大的收益呢？在限定条件内找到最佳的物品组合，这样的问题统称为背包问题。

根据限定的条件不同，背包问题还可以细分：

• 部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包；
• 0-1 背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品的 1/3 装入背包”的情况；
• 完全背包问题：不对每一件物品的数量做限制，同一件物品可以选择多个装入背包；
• 多重背包问题：每件物品的数量是有严格规定的，比如物品 A 有 2 件，物品 B 有 3 件。

前面章节中，我们学会了用贪心算法解决部分背包问题。本节，我们学习如何用动态规划算法解决 0-1 背包问题。

动态规划解决01背包问题

虚拟一个场景，商店中拥有 5 件商品，它们各自的重量和收益分别是：

• 商品 1：重量 1 斤，收益 1 元；
• 商品 2：重量 2 斤，收益 6 元；
• 商品 3：重量 5 斤，收益 18 元；
• 商品 4：重量 6 斤，收益 22 元；
• 商品 5：重量 7 斤，收益 28 元。

所有商品不可再分，顾客要么“整件”购买商品，要么放弃购买。一个小偷想窃取商品，他的背包只能装 11 斤商品，如何选择商品才能获得最大的收益呢？

动态规划算法解决此问题的核心思想是：背包承重 1 斤时所能获得的最大收益是很容易计算的，在此基础上，可以推算出背包承重 2 斤、3斤、...、14斤、15斤时所能获得的最大收益。建立如下这张表格，依次将各个商品装入不同承重的背包中，计算出它们所能获得的最大收益。

表1：动态规划算法解决01背包问题

表格中，wi 表示第 i 件商品的重量，vi 表示第 i 件商品的收益值。承重不同的各个背包尚未装入商品时，对应的收益值都为 0。

1) 首先考虑将商品一装入各个背包，除了承重值为 0 的背包，其它背包都能装入，且与不装任何商品相比，装入商品一后各个背包的收益更大，各个背包的收益值如表 2 所示：

表2：动态规划算法解决01背包问题

我们用 f(n) 表示承重值为 n 的背包对应的最大收益。从算法的角度，各个背包收益值是这样计算的：f(1)=1+f(0)、f(2)=1+f(1)、...、f(11)=1+f(10)，其中等号右侧表达式中的 1 指的是商品一的收益值，f(0)~f(10) 指的是不装任何商品时承重分别为 0~10 的背包对应的收益值，借助表格可以看到，它们的值都为 0。

2) 考虑将商品二装入各个背包，除了承重值为 0 和 1 的背包，其它背包都可以装入。我们可以计算出它们各自对应的收益值：

f(2) = 6 + f(0) = 6

f(3) = 6 + f(1) = 7

f(4) = 6 + f(2) = 7

...

f(9) = 6 + f(7) = 7

f(10) = 6 + f(8) = 7

f(11) = 6 + f(9) = 7

等号右侧 f(0)~f(9) 的值是表 2 中装入商品一的各个背包对应的收益值。相比装入商品一统计的各个背包的收益值，装入商品二能使提高各个背包的收益。更新后的表格为：

表3：动态规划算法解决01背包问题

3) 考虑将商品三装入各个背包，除了承重值为小于 5 的背包，其它背包都可以装入。我们可以计算出它们各自对应的收益值：

f(5) = 18 + f(0)  = 18

f(6) = 18 + f(1) = 19

f(7) = 18 + f(2) = 24

f(8) = 18 + f(3) = 25

f(9) = 18 + f(4) = 25

f(10) = 18 + f(5) = 25

f(11) = 18 + f(6) = 25

等号右侧 f(0)~f(6) 的值是表 2 中装入商品二的各个背包对应的收益值。和装入商品二时统计的各个背包的收益值相比，装入商品三能提高各个背包的收益。更新后的表格为：

表4：动态规划算法解决01背包问题

4) 采用同样的方法，我们可以将表 4 中缺失的数据补全，最终得到的表格为：

表5：动态规划算法解决01背包问题

注意，并不是每试图装入一个新商品，背包的收益一定会提高。举个例子，承重为 7 斤的背包装入商品四时的最大收益是：f(7) = 22+f(1) = 23，装入商品三时最大的收益值为：f(7) = 18+f(2) = 24。因此，表 5 中承重 7 斤的背包装入商品 4 时对应的收益值仍为 24，并未发生改变。

结合表 5，当背包承重为 11 斤时，所能获得的最大收益为 40 元。如下以伪代码的形式给大家总结了以上推理的整个过程：

输入 N    // 指定商品种类

输入 W    // 指定背包载重量

//w[] 记录各个商品的载重量，v[] 记录各个商品对应的收益

knapsack01(w[] , v[]):

   //逐个遍历每个商品

   for i <- 1 to N：

       //求出从 1 到 W 各个载重量对应的最大收益

       for j <- 1 to W:

           //如果背包载重量小于商品总重量，则商品无法放入背包，收益不变

           if  j < w[i]:

               result[i][j] = result[i-1][j]

           else:

               //比较装入该商品和不装该商品，哪种情况获得的收益更大，记录最大收益值

               result[i][j] = max(result[i-1][j] , v[i]+result[i-1][j-w[i]])

   return result