[問題] 關於背包問題

看板CSSE作者justim (透明石油)時間15年前 (2009/01/18 17:16)推噓2(2推 0噓 3→)

留言5則, 4人參與討論串1/1

最近在研究背包 (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

推

wa120

01/20 20:10, , 1^F

01/20 20:10, 1^F

推

hardcover

01/23 00:04, , 2^F

01/23 00:04, 2^F

→

gozule

01/23 00:31, , 3^F

01/23 00:31, 3^F