［演算法］ 0／1 knapsack problem

看板Grad-ProbAsk作者 (wtlee)時間8年前 (2017/10/16 12:03), 8年前編輯推噓4(4推 0噓 12→)
留言16則, 4人參與, 8年前最新討論串1/1
各位好,想請問 0/1 knapsack problem的時間複雜度為O(nW)其中W因為是用binary表示,所以實際上upper bound為指數,不知道這樣理解對不對? 但是這樣，那n用binary表示，不就還要再取lg ? ----- Sent from JPTT on my OPPO R7sf. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.227.170 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508126638.A.F62.html
→
10/16 12:55, 8年前 , 1F
please google pseudo-polynomial time
10/16 12:55, 1F
好 我再研究看看 謝謝！
推
10/16 13:08, 8年前 , 2F
平常我們的n，input size指的是"程式執行次數"，這
10/16 13:08, 2F
→
10/16 13:08, 8年前 , 3F
裡的input W則是variable。 假如變數為4, 在memory
10/16 13:08, 3F
→
10/16 13:08, 8年前 , 4F
裡則佔lg4=2, 但是程式執行次數實際上為4次(2^2)，
10/16 13:08, 4F
→
10/16 13:08, 8年前 , 5F
所以為指數成長
10/16 13:08, 5F
似懂非懂 我再想想 謝謝！！
推
10/16 15:31, 8年前 , 6F
我覺的課本應該是假設W比n大很多，大到我們根本沒辦法
10/16 15:31, 6F
→
10/16 15:31, 8年前 , 7F
用固定的bit數去表示，所以他才將W化成2^m，而n因為比
10/16 15:31, 7F
→
10/16 15:31, 8年前 , 8F
較小，可以用固定bit去表示，e.g. n=32k or n=64k，所以
10/16 15:31, 8F
→
10/16 15:31, 8年前 , 9F
O(32k*2^m)=O(k*2^m)，n有沒有化成bit數並不影響整個時
10/16 15:31, 9F
→
10/16 15:31, 8年前 , 10F
間複雜度。
10/16 15:31, 10F
感覺比較像c大說的那樣 是次數跟數值 兩個不一樣 因為課本題目最大負重也假設5而已 而且負重bit數 以常理想也不會太大吧？ ※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 16:32:28 ※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 16:40:03 ※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 16:44:08
推
10/16 18:30, 8年前 , 11F
10/16 18:30, 11F
→
10/16 18:30, 8年前 , 12F
-pseudopolynomial-time-how-does-it-differ-from-polyn
10/16 18:30, 12F
→
10/16 18:30, 8年前 , 13F
omial-time我是看這篇的，因為如果n指的是程式執行次數
10/16 18:30, 13F
→
10/16 18:30, 8年前 , 14F
而不用化成bit數的話，文章下面那個isPrime(n)時間複雜
10/16 18:30, 14F
→
10/16 18:30, 8年前 , 15F
度應該為O(n)（這個function只執行n-2次）
10/16 18:30, 15F
我的理解是 因為他這個n指的是數值 因為他判斷是不是質數 跟knapsack指的次數不一樣 ※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 19:40:33
推
10/16 19:48, 8年前 , 16F
#1N-azPo9 我以前回答過類似問題
10/16 19:48, 16F
我懂了 寫的超詳細 感謝！！！！！ ※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 20:38:37
‣ 更多 q1qip123 的文章
文章代碼(AID): #1Pv2-kzY (Grad-ProbAsk)