作者justim (透明石油)
看板CSSE
标题[问题] 关於背包问题
时间Sun Jan 18 17:16:03 2009
最近在研究 背包 (knapsack) 问题 (主要是 0/1 knapsack)。
就以前在学校的经验，总以为 dynamic programming 就是 knapsack problem
的唯一解法了。後来找了找文献後，才发现有另一群研究人员用 branch and bound
的方法来解。但看了看这些文献後觉得不太能分办这两种方法的优劣，所以上这个
板来问问。
就我个人的感觉而言，branch and bound 方法似乎比 dynamic programming 来得
有效率，但其空间复杂度却较 dynamic programming 来得高。
请问我这样的理解是对的吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.116.247.169
1F：推 wa120:背包问题 有更多的解法... 01/20 20:10
2F：推 hardcover:空间复杂度应该是dp比较高 01/23 00:04
3F：→ gozule:DP是有效率的暴力法，是要把解都算出来再去比最佳解 01/23 00:31
4F：→ nick23:b&b的效率与空间复杂度是取决於ub,lb与分支方式来决定的 01/24 11:33
5F：→ nick23:若设计的好,就可以大量减少结点..若是不好那候选人就多啦! 01/24 11:35