文章标签 ‘分支界限’

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

2015年9月7日 没有评论

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

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

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

2015年8月24日 没有评论

哪能搞法——分支界限

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

fulltree

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

阅读全文…