前面的方法已经非常快了，应该说很满意。那还有没有再优化的余地呢？
我们再来仔细看一下这个过程：深度优先搜索，逐级回溯，典型的二叉树遍历方式。为了方便说明，我标出了结点遍历的顺序：
Continue reading “0-1 背包问题详解 (4)”
标签： 分支界限
0-1 背包问题详解 (3)
哪能搞法——分支界限
我们先把动态规划的想法放一下，退一步来看看这个问题。每一个物品都可能放或者不放，如果用一个决策树来表示的话，就得到这样一棵满二叉树：
这对于 \(n\) 个物品就有 \(2^n\) 种放法，总共要计算 \(2^{n+1} – 2\) 个结点，当然是太多了。不过，有没有什么办法能让遍历的结点少一点呢？