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

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

2015年9月7日 发表评论 阅读评论

前面的方法已经非常快了,应该说很满意。那还有没有再优化的余地呢?

我们再来仔细看一下这个过程:深度优先搜索,逐级回溯,典型的二叉树遍历方式。为了方便说明,我标出了结点遍历的顺序:
knapsack_tiny_arrow

一切看起来都挺好的。不过再仔细看一下——hmm,似乎还是有些地方可以琢磨琢磨。比如说,遍历到第二个物品,也就是价值 50,重量 9,价值上限为 60 的那个结点的时候,旁边那个价值 30 的结点的价值上限却是 76.7。也就是说,我们现在遍历的这个结点,其实“希望”并不如另外的那个大。而最终结果也证明,沿着价值上限为 60 的结点找下去似乎是多做了“无用功”,而全局最大值正是在那个价值上限为 76.7 的结点之下。

这就给我们一个启发——价值上限最大的结点,是不是更可能是拥有全局最大价值呢?即便不是,价值上限大,也更有可能更快地达到较高的价值,从而更快地提高 maxValue,剪掉更多毫无希望的枝节。

那么如何实现呢?现在下一个遍历结点的是从栈中弹出的,弹出的顺序取决于元素压栈的顺序。有什么办法能让弹出的顺序和价值上限相关呢?价值上限越大的优先级越高——啊哈,优先队列!Python 里面实现起来再容易不过了,因为它提供了 heapq 这个二叉堆。不过这个堆默认是最小堆,也就是堆顶上的元素是最小的。怎么把它变成最大堆呢?只要把元素取相反数就可以了嘛。实现起来只需要在原来的程序上稍作改动:

那么这次的遍历顺序变成什么样了呢?

knapsack_tiny_pq_arrow

虽然看着有点眼花缭乱,但其实很明确——找价值上限最高的那个。另外你注意到了吗?遍历的结点少了一个!也许你会说这少一个有什么大不了的……可是元素一多可就显出来啦!比如这个大包包,原先的方法遍历了多少个结点呢?8512 个。换用二叉堆之后呢?只有 2618 个!而这个有 10000 个元素的大包包呢?遍历结点数从 246426 降到了 47445,运行时间不到原先的三分之一(虽然原先也才 0.6 秒)!

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

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

%d 博主赞过: