首页 > 技术相关 > 0-1 背包问题详解 (1)

0-1 背包问题详解 (1)

2015年8月17日 发表评论 阅读评论

所有代码可见于:https://github.com/jameslao/Algorithmic-Pearls/tree/master/0-1-Knapsack

为什么要写这个系列

这些程序大部分都是 2013 年跟着 Tim Roughgarden 看算法课的时候写的,还算有些心得,尤其是优化的部分,似乎中文书中讲到的不是很多。而且也很久没有写博客了,回顾一下当初学过的东西也还有些收获。

背包问题是啥

不知道你还记不记得我们小时候看过的《太阳山》的故事:

cover

从前,有弟兄俩,老大是个贪心的富人,老二是个穷人。

老二没有地,种老大的地。他一年到头在地里做活;可是老是吃不上,穿不上,租子交不够。

有一天,老二上山打柴。天都快黑了,他还坐在山上;他发愁,加上打柴,租子还是交不够。这时候,忽然刮起一阵黑风,飞来一只大鸟。大鸟落在他跟前,对他说:“你不用发愁。太阳山上有很多金子、银子,还有宝石。我背你上太阳山去吧!你从那儿可以拿些金子回来。”

老二爬到大鸟的背上。大鸟叫他闭上眼睛。他刚闭上眼睛,觉得飕一下子,就听见大鸟说:“到了。你看,有多少金子!去拿吧!你可不要贪心。这是太阳山。如果我们在这儿待得时间太长,赶上太阳回来,就把你烧死了。那时候,我也没办法救你。”

老二一边答应着,一边从大鸟的背上跳下来。哎呀!遍地是金子、银子、宝石,金光闪闪,晃得人睁不开眼睛。老二想了想,就拿一小块金子,装进口袋,要大鸟背他回去。大鸟问他为什么只拿一小块儿。他说够了。

老二又爬到大鸟的背上,闭上眼睛。飕一下子,大鸟落到他家门口了。他谢过大鸟,大鸟就飞走了。

老二有了金子,买了地,盖了房子。他早晨起来去种地,晚上回到新盖的房子里休息,日子过得很好。

老大见老二有金子,很眼红。他问老二的金子是哪儿来的。老二把大鸟背自己到太阳山的事告诉他了。

第二天,老大学着老二到山上去打柴。天快黑了,他故意不回家,坐在山上假装发愁。大鸟飞来了,也答应背他上太阳山去拿些金子。

大鸟背老大到了太阳山,嘱咐他不要贪心,像嘱咐老二一样,可是他连哼也不哼。他看见那么多金子、银子、宝石,忙着张开大布袋子,捡最大块儿的金子往里装。

老大拼命的往大布袋子里装金子,装个没完。大鸟催他回去,他说再让他拿几块。大鸟再催他回去,他还是这么说。最后,大鸟说:“时候到了!太阳马上就回来了!”他这才站起来,朝着大鸟走,摇摇晃晃的,大布袋子压得他走不稳了。没走几步,他又弯下腰来,说:“等一会儿。我再拿几颗宝石吧!”

正在这时候,火红的太阳回来了。它把烈火似的阳光喷到太阳山上。大鸟飞走了。老大被烧死了。

要是换你去拿,你会怎么拿呢?你是只拿一小块,还是拿到自己走不动?有没有什么办法,能够拿到最多的金子呢?

所谓背包 (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,有这样几件物品:

物品 价值 重量
1 30 4
2 20 5
3 40 10
4 10 3

我们按照前面的思路,写出来的代码是这样的:

这里利用了 python 允许数组下标为负,即 F[-1] 实际上就是 F[n],可以减少一些边界条件的处理。最后显示加入了哪些物品时,只需对所有物品进行回溯,看看在哪个物品上导致 F 增加,即说明这个物品被加入了背包里。

运行结果是

我顺便打印了 F 好让大家有一个更直观的感觉:

这里有一个稍微大一点的例子,运行之后会输出结果:

看到这两个循环,很明显这个算法的时间复杂度是 $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)$ 啦!

基本上,一般的书讲背包算法的动态规划也就到此为止了。真的就到此为止了吗?$O(nW)$ 就让我们满意了吗?你想想看,这玩意和 $W$ 相关,可 $W$ 是一个数字啊!我们哪天要是不开心买了个大包包难道就要算好久好久了吗?(有兴趣的可以试试……)

欲知后事如何,且听下回分解

更多算法内容请见《算法拾珠》

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

%d 博主赞过: