背包问题
有负重上限的徒步者、拿着麻袋的小偷、有预算和一串项目清单的公司:他们都面对同一个问题。放进哪些东西,才能在不超过上限的情况下得到最多的价值?这就是背包问题。当重量是大小适中的整数时,动态规划可以精确地求解它。
问题
有 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 密码系统就建立在背包问题之上,几年后被攻破。
动手探索
打开应用,切换到“表格”视图,按“单步”。橙色格子正在被填写,蓝色格子是它比较的两个格子:正上方的格子,以及上一行中向左移动该物品重量的格子。最后一个格子填完后,倒推过程用橙色从右下角向上攀升,装入的物品显示在表格下方。
常见问题
0/1 背包、多重背包和完全背包有什么区别?
在 0/1 背包中,每个物品最多取一次。在多重背包(有界背包)中,每个物品的数量有限;在完全背包(无界背包)中,数量不限。它们之间的表格只有细微的变化。
贪心法对背包问题有正确的时候吗?
在物品可以分割的分数背包问题中,先取单位重量价值最高的物品是最优的。对于整个的物品,结果可能差得很远;不过,贪心法的结果和单个最有价值物品两者中较好的那个,总是至少有最佳价值的一半。
表格需要多少内存?
完整的表格需要 (n + 1)·(W + 1) 个格子,倒推出物品就需要它。如果只要最佳价值,一行 W + 1 个格子就够了,从右往左填写。
背包问题和子集和问题一样吗?
子集和问题是一种特殊情况:每个物品的价值等于它的重量,问题是背包能否被恰好装满。它同样是 NP 完全的,也用同样的表格求解。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试背包问题