作者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