前面的方法已经非常快了，应该说很满意。那还有没有再优化的余地呢？
我们再来仔细看一下这个过程：深度优先搜索，逐级回溯，典型的二叉树遍历方式。为了方便说明，我标出了结点遍历的顺序：
一切看起来都挺好的。不过再仔细看一下——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 秒）！
更多算法内容请见《算法拾珠》。