前面的方法已经非常快了,应该说很满意。那还有没有再优化的余地呢?
我们再来仔细看一下这个过程:深度优先搜索,逐级回溯,典型的二叉树遍历方式。为了方便说明,我标出了结点遍历的顺序:
一切看起来都挺好的。不过再仔细看一下——hmm,似乎还是有些地方可以琢磨琢磨。比如说,遍历到第二个物品,也就是价值 50,重量 9,价值上限为 60 的那个结点的时候,旁边那个价值 30 的结点的价值上限却是 76.7。也就是说,我们现在遍历的这个结点,其实“希望”并不如另外的那个大。而最终结果也证明,沿着价值上限为 60 的结点找下去似乎是多做了“无用功”,而全局最大值正是在那个价值上限为 76.7 的结点之下。
这就给我们一个启发——价值上限最大的结点,是不是更可能是拥有全局最大价值呢?即便不是,价值上限大,也更有可能更快地达到较高的价值,从而更快地提高 maxValue
,剪掉更多毫无希望的枝节。
那么如何实现呢?现在下一个遍历结点的是从栈中弹出的,弹出的顺序取决于元素压栈的顺序。有什么办法能让弹出的顺序和价值上限相关呢?价值上限越大的优先级越高——啊哈,优先队列!Python 里面实现起来再容易不过了,因为它提供了 heapq
这个二叉堆。不过这个堆默认是最小堆,也就是堆顶上的元素是最小的。怎么把它变成最大堆呢?只要把元素取相反数就可以了嘛。实现起来只需要在原来的程序上稍作改动:
from heapq import * def knapsack(vw, limit): def bound(v, w, j): ... maxValue = 0 PQ = [[-bound(0, 0, 0), 0, 0, 0]] # -bound to keep maxheap while PQ: b, v, w, j = heappop(PQ) if b <= -maxValue: # promising if w + vw[j][1] <= limit: maxValue = max(maxValue, v + vw[j][0]) heappush(PQ, [-bound(v + vw[j][0], w + vw[j][1], j + 1), v + vw[j][0], w + vw[j][1], j + 1]) if j < len(vw) - 1: heappush(PQ, [-bound(v, w, j + 1), v, w, j + 1]) return maxValue
那么这次的遍历顺序变成什么样了呢?
虽然看着有点眼花缭乱,但其实很明确——找价值上限最高的那个。另外你注意到了吗?遍历的结点少了一个!也许你会说这少一个有什么大不了的……可是元素一多可就显出来啦!比如这个大包包,原先的方法遍历了多少个结点呢?8512 个。换用二叉堆之后呢?只有 2618 个!而这个有 10000 个元素的大包包呢?遍历结点数从 246426 降到了 47445,运行时间不到原先的三分之一(虽然原先也才 0.6 秒)!
更多算法内容请见《算法拾珠》。