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

哪能搞法——分支界限

我们先把动态规划的想法放一下,退一步来看看这个问题。每一个物品都可能放或者不放,如果用一个决策树来表示的话,就得到这样一棵满二叉树:

fulltree

这对于 \(n\) 个物品就有 \(2^n\) 种放法,总共要计算 \(2^{n+1} – 2\) 个结点,当然是太多了。不过,有没有什么办法能让遍历的结点少一点呢?

Continue reading “0-1 背包问题详解 (3)”

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

哪能搞法——动态规划再试

不知道有没有读者试过了这个大包包,我试了一下,在我的 2.30GHz i5 5300U 上,这个函数用 cPython 跑了…… 1632.07 秒,将近半个小时。照这个搞法,每次那个包有多大,就得搞出多少项。那个包的大小可是个任意数啊?这 $ W$ 比 $ 2^n$ 大都说不定呢?
Continue reading “0-1 背包问题详解 (2)”

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

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

为什么要写这个系列

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

背包问题是啥

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

cover

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

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

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

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

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

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

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

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

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

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

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

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

要是换你去拿,你会怎么拿呢?你是只拿一小块,还是拿到自己走不动?有没有什么办法,能够拿到最多的金子呢?
Continue reading “0-1 背包问题详解 (1)”