02-背包问题

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

9.1　背包问题

背包问题（knapsack problem）其实是一种常见的计算需求，给定一组有限的可选项，找出有限资源的最优用法，再把它编成一个有趣的故事。小偷进入一户人家要偷点儿东西。他有一个背包，背包的容纳能力限制了他能偷的物品。他怎样算出该把哪些物品放进背包呢？背包问题如图9-1所示。

图9-1　小偷必须得决定要偷哪些物品，因为背包的容纳能力有限

如果可以拿走任意数量的任意物品，那么小偷只需要简单地将每件物品的价值除以重量，就能求出可用容纳能力下价值最高的物品。但为了让场景更加真实，这里规定小偷不能拿走半件物品（如2.5台电视机）。于是我们有了求解小偷问题的0/1变体，因为多了一条必须执行的规则：小偷要么拿走整件物品，要么不拿。

首先，我们定义一个 NamedTuple 类型的类用于存放物品，具体代码如代码清单9-1所示。

代码清单9-1　knapsack.py

from typing import NamedTuple, List
class Item(NamedTuple):
    name: str
    weight: int
    value: float

如果想用蛮力法求解，我们就要查看可放入背包物品的每种组合。在数学上这被称为幂集，某集合（本示例中为物品的集合）的幂集可能有2^N种不同的子集，其中N是数据项的数量。因此，蛮力法需要分析2^N种组合，即复杂度为O(2^N)。如果数据项不多，那么这是可行的，但数据量很多时就难以维持了。任何步数为指数级的解法都是应该避免的。

这里将换用一种名为动态规划（dynamic programming）的技术，其在概念上类似于第1章中的结果缓存（memoization）。动态规划法不是用蛮力法一次性把问题全部解决，而是先解决构成大问题的子问题并保存结果，再利用这些缓存的结果来解决更大的问题。只要把背包的容纳能力计算方案看成离散的多个步骤，就可以用动态规划来解决背包问题。

例如，为了解决3斤容纳能力3件物品的背包问题，我们可以首先解决1斤容纳能力1件物品、2斤容纳能力1件物品、3斤容纳能力1件物品的问题。然后可以用求得的结果解决1斤容纳能力2件物品、2斤容纳能力2件物品、3斤容纳能力2件物品的问题。最后，我们可以解决全部3件物品的问题。

整个求解过程就是填表操作，给出每种物品和容纳能力组合的最优解。对于这里的函数，我们先要进行填表操作，然后根据表格得出解^[1]。具体代码如代码清单9-2所示。

代码清单9-2　knapsack.py（续）

def knapsack(items: List[Item], max_capacity: int) -> List[Item]:
   # build up dynamic programming table
   table: List[List[float]] = [[0.0 for _ in range(max_capacity + 1)] for _ in 
    range(len(items) + 1)]
   for i, item in enumerate(items):
       for capacity in range(1, max_capacity + 1):
           previous_items_value: float = table[i][capacity]
           if capacity >= item.weight: # item fits in knapsack
               value_freeing_weight_for_item: float = table[i][capacity - item.weight]
               # only take if more valuable than previous item
               table[i + 1][capacity] = max(value_freeing_weight_for_item + item.
                value, previous_items_value)
           else: # no room for this item
              table[i + 1][capacity] = previous_items_value
    # figure out solution from table
    solution: List[Item] = []
    capacity = max_capacity
    for i in range(len(items), 0, -1): # work backwards
        # was this item used?
        if table[i - 1][capacity] != table[i][capacity]:
            solution.append(items[i - 1])
            # if the item was used, remove its weight
            capacity -= items[i - 1].weight
    return solution

上述函数第一部分的内层循环将执行N×C次，其中N是物品数量，C是背包的最大容纳能力。因此，该算法将执行O(N×C)次，当物品数量较多时这明显比蛮力法进步很多。例如，对于代码清单9-3中的11件物品，蛮力法需要检查2¹¹（2048）种组合。因为这里背包的最大容纳能力是75个单位，所以上述动态规划函数将执行825次（11×75）。随着物品数量的增加，这种差别将会呈指数级扩大。

下面看一下实际的求解结果，如代码清单9-3所示。

代码清单9-3　knapsack.py（续）

if __name__ == "__main__":
    items: List[Item] = [Item("television", 50, 500),
                         Item("candlesticks", 2, 300),
                         Item("stereo", 35, 400),
                         Item("laptop", 3, 1000),
                         Item("food", 15, 50),
                         Item("clothing", 20, 800),
                         Item("jewelry", 1, 4000),
                         Item("books", 100, 300),
                         Item("printer", 18, 30),
                         Item("refrigerator", 200, 700),
                         Item("painting", 10, 1000)]
    print(knapsack(items, 75))

请查看输出到控制台的结果，最优解将是“painting、jewelry、clothing、laptop、stereo和candlestick”。下面给出了一些输出的例子，列出了给定容纳能力有限的背包时小偷应该窃取哪些物品才最值钱：

[Item(name='painting', weight=10, value=1000), Item(name='jewelry', weight=1, value=4000),
     Item(name='clothing', weight=20, value=800), Item(name='laptop', weight=3, 
     value=1000),  Item(name='stereo', weight=35, value=400), Item(name='candlesticks',
     weight=2, value=300)]

为了更好地理解该函数的工作原理，下面我们介绍一些它的细节：

for i, item in enumerate(items):
    for capacity in range(1, max_capacity + 1):

对于每种可能的物品数量，我们都将线性遍历所有容纳能力，直到达到背包的最大容纳能力。请注意，这里是“每种可能的物品数量”，而不是每一件物品。当 i 等于2时，它不是代表第2件物品，而是代表在每个已搜索的容纳能力以内前两件物品的可能组合。 item 是正要被窃取的下一件物品：

previous_items_value: float = table[i][capacity]
if capacity >= item.weight: # item fits in knapsack

previous_items_value 是正在探索的当前 capacity 以内最后一种物品组合的价值。对于每种可能的物品组合，我们都要考虑是否还有可能加入最“新”的物品。

如果物品的总重量超过了当前背包的容纳能力，我们只需复制当前容纳能力以内的最后一种物品组合的价值：

else: # no room for this item
    table[i + 1][capacity] = previous_items_value

否则，我们就要考虑在当前容纳能力以内，加入“新”物品能否产生比最后一种物品组合更高的价值。只要将该物品的价值加上表中已算出的价值即可得知，表中已算出的价值是指从当前容纳能力中减去该物品重量后的容纳能力对应的最近一次物品组合的价值。如果总价值高于当前容纳能力下的最后一种物品组合的价值，就将其插入表，否则，就插入最后一种组合的价值：

value_freeing_weight_for_item: float = table[i][capacity - item.weight]
# only take if more valuable than previous item
table[i + 1][capacity] = max(value_freeing_weight_for_item + item.value,  previous_
     items_value)

至此，建表的工作就完成了。但是，要想真正得到结果中的物品，需要从最高容纳能力值及最终求得的物品组合开始往回找：

for i in range(len(items), 0, -1): # work backwards
    # was this item used?
    if table[i - 1][capacity] != table[i][capacity]:

我们从最终位置开始，自右到左遍历缓存表，检查插入表的总价值是否有变化。如果有，就意味着在计算某组合时加入了新的物品，因为该组合比前一组合价值高。于是我们把该物品加入解。同时，要从总的容纳能力中减去该物品的重量，可以想象为在表中向上移动：

solution.append(items[i - 1])
# if the item was used, remove its weight
capacity -= items[i - 1].weight

注意　或许大家已经看到了，在构建表和查找解的过程中，有些迭代器的操作次数多了1次，表的大小也多了1格。这是为了便于编程。请考虑一下背包问题自底向上的构建过程。一开始我们需要处理容纳能力为0的背包。如果从表的底部开始向上工作，那么我们需要额外的行和列的原因就很好理解了。

还有困惑吗？表9-1就是由 knapsack() 函数构建的表。之前的问题需要相当大的一张表，所以不妨就看一张3斤容纳能力的背包和3件物品构成的表：火柴（1斤）、手电筒（2斤）和书（1斤）。假设这些物品的价值分别为5美元、10美元和15美元。

表9-1　3件物品的背包问题示例

| 0斤 | 1斤 | 2斤 | 3斤 | | :----- | :----- | :----- | :----- | :----- | :----- | | 火柴（1斤、5美元） | 0 | 5 | 5 | 5 | | 手电筒（2斤、10美元） | 0 | 5 | 10 | 15 | | 书（1斤、15美元） | 0 | 15 | 20 | 25 |

从左往右看这张表，要装入背包的重量在不断增加。从上往下看这张表，要装的物品数量在增加。第一行，只尝试装入火柴。第二行，装入背包所能容纳的价值最高的火柴和手电筒的组合。第三行，装入价值最高的3种物品的组合。

请试着自行填写一下上述的空白表格吧，采用 knapsack() 函数中的算法和以上3种物品，就当这是帮助你理解的练习吧。然后用函数尾部的算法从表中取回正确的物品组合。这张表对应的就是函数中的 table 变量。

Previous 上一篇本节目录 Next 下一篇

02-背包问题

9.1 背包问题

9.1　背包问题