背包问题

有负重上限的徒步者、拿着麻袋的小偷、有预算和一串项目清单的公司:他们都面对同一个问题。放进哪些东西,才能在不超过上限的情况下得到最多的价值?这就是背包问题。当重量是大小适中的整数时,动态规划可以精确地求解它。

一张以物品为行、容量为列的表格,倒推路径用橙色标出,旁边是一个背包和大小不同的物品
一张以物品为行、容量为列的表格,倒推路径用橙色标出,旁边是一个背包和大小不同的物品

问题

有 n 个物品,每个都有重量和价值,还有一个最多能装重量 W 的背包。选出一组物品,使总重量不超过 W,且总价值尽可能大。每个物品要么整个装入,要么不装,所以叫 0/1 背包问题。n 个物品有 2ⁿ 种可能的组合,所以全部尝试很快就变得不可能。

表格

设 best[i][w] 为只用前 i 个物品时,重量 w 内能装下的最大价值。那么 best[0][w] = 0,之后每一行有两种选择:不装物品 i,得到 best[i − 1][w];或者如果它的重量 wᵢ 装得下,就装入它,得到它的价值加上 best[i − 1][w − wᵢ]。较大者就是 best[i][w]。逐行填表,就能保证所需的两个格子总是已经算好。

一个例子

设容量为 7,有四个物品,重量为 1、3、4、5,价值为 1、4、5、7。只有第一个物品时,从 1 开始的每个容量价值都是 1。加入第二个后,容量 4 能同时装下两个,价值 5。加入第三个后,容量 7 能装下物品 2 和 3,价值 9。第四个物品重 5、价值 7,在容量 6 或 7 时可以和物品 1 一起得到 8,但 9 更好,所以右下角的格子是 9:装入重量为 3 和 4 的物品。

它有多难?

表格大约需要 n·W 步。看起来很快,但 W 是一个数,一个 d 位数可以大到 10 的 d 次方,所以工作量随输入长度呈指数增长。背包问题是 NP 困难的;它是理查德·卡普 1972 年提出的 21 个 NP 完全问题之一。在实际中,表格法、分支定界法和好的近似方案都能很好地处理大型的实际问题。

历史与应用

这个名字可以追溯到 20 世纪初的数学家托比亚斯·丹齐格,他的儿子乔治·丹齐格在 1957 年为它给出了一个经典的贪心方法。背包问题出现在预算编制和投资组合选择中,出现在尽量减少浪费地切割原材料、装载货物中,甚至出现在早期的公钥密码学中:1978 年的 Merkle–Hellman 密码系统就建立在背包问题之上,几年后被攻破。

乔治·丹齐格(左)1976年从总统杰拉尔德·福特手中接受国家科学奖章。1957年,丹齐格给出了背包问题的一种经典贪心方法。这一名称本身可追溯到他的父亲托比亚斯·丹齐格。
乔治·丹齐格(左)1976年从总统杰拉尔德·福特手中接受国家科学奖章。1957年,丹齐格给出了背包问题的一种经典贪心方法。这一名称本身可追溯到他的父亲托比亚斯·丹齐格。

动手探索

打开应用,切换到“表格”视图,按“单步”。橙色格子正在被填写,蓝色格子是它比较的两个格子:正上方的格子,以及上一行中向左移动该物品重量的格子。最后一个格子填完后,倒推过程用橙色从右下角向上攀升,装入的物品显示在表格下方。

常见问题

0/1 背包、多重背包和完全背包有什么区别?

在 0/1 背包中,每个物品最多取一次。在多重背包(有界背包)中,每个物品的数量有限;在完全背包(无界背包)中,数量不限。它们之间的表格只有细微的变化。

贪心法对背包问题有正确的时候吗?

在物品可以分割的分数背包问题中,先取单位重量价值最高的物品是最优的。对于整个的物品,结果可能差得很远;不过,贪心法的结果和单个最有价值物品两者中较好的那个,总是至少有最佳价值的一半。

表格需要多少内存?

完整的表格需要 (n + 1)·(W + 1) 个格子,倒推出物品就需要它。如果只要最佳价值,一行 W + 1 个格子就够了,从右往左填写。

背包问题和子集和问题一样吗?

子集和问题是一种特殊情况:每个物品的价值等于它的重量,问题是背包能否被恰好装满。它同样是 NP 完全的,也用同样的表格求解。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试背包问题