所有代码可见于:https://github.com/jameslao/Algorithmic-Pearls/tree/master/0-1-Knapsack
为什么要写这个系列
这些程序大部分都是 2013 年跟着 Tim Roughgarden 看算法课的时候写的,还算有些心得,尤其是优化的部分,似乎中文书中讲到的不是很多。而且也很久没有写博客了,回顾一下当初学过的东西也还有些收获。
背包问题是啥
不知道你还记不记得我们小时候看过的《太阳山》的故事:
从前,有弟兄俩,老大是个贪心的富人,老二是个穷人。
老二没有地,种老大的地。他一年到头在地里做活;可是老是吃不上,穿不上,租子交不够。
有一天,老二上山打柴。天都快黑了,他还坐在山上;他发愁,加上打柴,租子还是交不够。这时候,忽然刮起一阵黑风,飞来一只大鸟。大鸟落在他跟前,对他说:“你不用发愁。太阳山上有很多金子、银子,还有宝石。我背你上太阳山去吧!你从那儿可以拿些金子回来。”
老二爬到大鸟的背上。大鸟叫他闭上眼睛。他刚闭上眼睛,觉得飕一下子,就听见大鸟说:“到了。你看,有多少金子!去拿吧!你可不要贪心。这是太阳山。如果我们在这儿待得时间太长,赶上太阳回来,就把你烧死了。那时候,我也没办法救你。”
老二一边答应着,一边从大鸟的背上跳下来。哎呀!遍地是金子、银子、宝石,金光闪闪,晃得人睁不开眼睛。老二想了想,就拿一小块金子,装进口袋,要大鸟背他回去。大鸟问他为什么只拿一小块儿。他说够了。
老二又爬到大鸟的背上,闭上眼睛。飕一下子,大鸟落到他家门口了。他谢过大鸟,大鸟就飞走了。
老二有了金子,买了地,盖了房子。他早晨起来去种地,晚上回到新盖的房子里休息,日子过得很好。
老大见老二有金子,很眼红。他问老二的金子是哪儿来的。老二把大鸟背自己到太阳山的事告诉他了。
第二天,老大学着老二到山上去打柴。天快黑了,他故意不回家,坐在山上假装发愁。大鸟飞来了,也答应背他上太阳山去拿些金子。
大鸟背老大到了太阳山,嘱咐他不要贪心,像嘱咐老二一样,可是他连哼也不哼。他看见那么多金子、银子、宝石,忙着张开大布袋子,捡最大块儿的金子往里装。
老大拼命的往大布袋子里装金子,装个没完。大鸟催他回去,他说再让他拿几块。大鸟再催他回去,他还是这么说。最后,大鸟说:“时候到了!太阳马上就回来了!”他这才站起来,朝着大鸟走,摇摇晃晃的,大布袋子压得他走不稳了。没走几步,他又弯下腰来,说:“等一会儿。我再拿几颗宝石吧!”
正在这时候,火红的太阳回来了。它把烈火似的阳光喷到太阳山上。大鸟飞走了。老大被烧死了。
要是换你去拿,你会怎么拿呢?你是只拿一小块,还是拿到自己走不动?有没有什么办法,能够拿到最多的金子呢?
所谓背包 (knapsack) 问题,就是说一个要去爬山的人(或者大盗之类的也行),他有很多东西可以带,他的包也足够大,但是背得动的总重量有一个上限 $ W$ (大家都是人)。假设我们一共有 $ n$ 种物品,每件物品 $ j$ 都有一个非负的重量 $ w_j$(氢气球之类不算)和一个非负的价值 $ v_j$ (我就不举例了)。那么应该怎样挑选,才能让背包中装的物品的总价值最高?
也就是说要让目标函数
$$
\sum_{j=1}^n v_j x_j
$$
最大化。
如果每种物品只有一件,要么带要么不带,那就是最基本的 0-1 背包问题 。这时要满足约束条件
$$
\sum_{j=1}^n w_j x_j \le W, \; x_j \in \{0, 1\}.
$$
如果物品 $j$ 有最多 $b_j$ 件可拿,就称为多重背包问题或者有界背包问题,约束条件是
$$
\sum_{j=1}^n w_j x_j \le W, \; x_j \in \{0, 1, \ldots, b_j\}.
$$
如果可以敞开拿呢,就称为完全背包问题或者无界背包问题 。
这问题有啥搞头
我这么宅的人,一年也不会出去背包几趟,我也没那个机会去太阳山拣金子宝石或者去抢珠宝店,犯得着费这个劲研究这东西吗?
但是——比如说你有一笔钱来投资,有 $n$ 种可能的投资选择,投资 $j$ 需要 $w_j$ 的资金,会创造 $v_j$ 的收益(这儿先不说风险的事儿……)。那解决了这个背包问题,不就得出了一个获得最大收益的最优组合吗?还有比如货轮装货,也是类似的问题。
除了前面提到的这些实际应用,0-1 背包问题的意义还在于它是最简单的整数规划问题,并且可以为许多复杂问题提供一个解决的途径。
可是我们有电脑呀,算一下还不快吗?最暴力的方法就是检查所有可能的 $x_j$ 组合,选出来最优的就行了。可是这个组合有 $2^n$ 个,只要 $n$ 稍微大一点点,就已经超出了计算机能够解决的范畴了(你可以算一下比如 $2^{64}$ 会怎么样……)。
多年来,人们对这个看似简单的问题做出了相当多的研究,也得出了若干种能够比较高效解决这个问题的方法,成千上万个物品也不在话下了。我们后面一一加以介绍。
哪能搞法——动态规划初试
现在一共有 $n$ 个物品要考虑,总重量不超过 $W$。我们倒着来考虑一下,最优的背包中,包含不包含第 $n$ 个物品呢?
- 如果不包含第 $n$ 个物品,那么这个物品就可以直接去掉了,最优解就是只有前 $n-1$ 个物品放在 $W$ 的背包中的结果;
- 如果包含第 $n$ 个物品,那背包就被它占掉了 $w_n$ ,现在的问题就是要把前 $n-1$ 个物品放在 $W – w_n$ 的背包中怎么放法了。
看出来了吗?这两种情况中,总价值比较高的就是我们所要的最优解。如果用 $f_n(W)$ 来表示总价值的话,那么
$$
f_n(W) = \max \begin{cases}
f_{n-1} (W) \\
f_{n-1} (W – w_n) + v_n
\end{cases}
$$
这就是我们所要的状态转移方程。
空说不太好说,我们来举一个具体的例子吧。为了方便起见,我们规定输入的格式是这样的:第一行的两个数分别是重量上限 $W$ 和物品总数 $n$,接下来的每一行则是物品的价值 $v_j$ 和重量 $w_j$。比方说输入文件是:
16 4 30 4 20 5 40 10 10 3
意思是我们的背包总重不超过 16,有这样几件物品:
物品 | 价值 | 重量 |
---|---|---|
1 | 30 | 4 |
2 | 20 | 5 |
3 | 40 | 10 |
4 | 10 | 3 |
我们按照前面的思路,写出来的代码是这样的:
#!/usr/bin/env python3 import sys def knapsack(v, w, limit, n): F = [[0] * (limit + 1) for x in range(n + 1)] for i in range(0, n): # F[-1] is all 0. for j in range(limit + 1): if j >= w[i]: F[i][j] = max(F[i - 1][j], F[i - 1][j - w[i]] + v[i]) else: F[i][j] = F[i - 1][j] return F if __name__ == "__main__": with open(sys.argv[1] if len(sys.argv) > 1 else sys.exit(1)) as f: limit, n = map(int, f.readline().split()) v, w = zip(*[map(int, ln.split()) for ln in f.readlines()]) F = knapsack(v, w, limit, n) print("Max value:", F[n - 1][limit]) """ Display selected items""" y = limit for i in range(n - 1, -1, -1): if F[i][y] > F[i - 1][y]: print ("item: ", i, "value:", v[i], "weight:", w[i]) y -= w[i]
这里利用了 python 允许数组下标为负,即 F[-1]
实际上就是 F[n]
,可以减少一些边界条件的处理。最后显示加入了哪些物品时,只需对所有物品进行回溯,看看在哪个物品上导致 F
增加,即说明这个物品被加入了背包里。
运行结果是
Max value: 12248 Max value: 70 item: 2 value: 40 weight: 10 item: 0 value: 30 weight: 4
我顺便打印了 F
好让大家有一个更直观的感觉:
[0, 0, 0, 0, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30] [0, 0, 0, 0, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 50, 50, 50] [0, 0, 0, 0, 30, 30, 30, 30, 30, 50, 50, 50, 50, 50, 70, 70, 70] [0, 0, 0, 10, 30, 30, 30, 40, 40, 50, 50, 50, 60, 60, 70, 70, 70] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
这里有一个稍微大一点的例子,运行之后会输出结果:
Max value: 12248 item: 13 value: 3878 weight: 9656 item: 12 value: 1513 weight: 3926 item: 7 value: 2890 weight: 7280 item: 5 value: 1022 weight: 2744 item: 2 value: 2945 weight: 7390
看到这两个循环,很明显这个算法的时间复杂度是 $O(nW)$,这个数组 F
的空间复杂度也是 $O(nW)$。能不能稍微改得好一点呢?
从上面这个循环中我们发现,最重要的值实际上是 F[n-1]
,前面的那些值我们并不太关心。那能不能不要保留这些值呢?如果我们原地刷新 F[i][j] = max(F[i][j], F[i][j - w[i]] + v[i])
…… 不行,这样的话,如果左边的 j
先被刷新,右边再碰到同样的 j - w[i]
就已经不是上一轮的值了。那么……要是换从右边开始更新呢?那就没问题啦!咱们的空间复杂度就降到 $O(W)$ 啦!
def knapsack(v, w, limit, n): F = [0] * (limit + 1) for i in range(n): for j in range(limit, w[i], -1): F[j] = max(F[j - w[i]] + v[i], F[j]) return F
基本上,一般的书讲背包算法的动态规划也就到此为止了。真的就到此为止了吗?$O(nW)$ 就让我们满意了吗?你想想看,这玩意和 $W$ 相关,可 $W$ 是一个数字啊!我们哪天要是不开心买了个大包包难道就要算好久好久了吗?(有兴趣的可以试试……)
欲知后事如何,且听下回分解。
更多算法内容请见《算法拾珠》。