［演算法］ 0／1 knapsack problem

[q1qip123 (wtlee)]

各位好,想請問
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
→ s89162504: please google pseudo-polynomial time
好 我再研究看看 謝謝！
推 clonsey1314: 平常我們的n，input size指的是"程式執行次數"，這
→ clonsey1314: 裡的input W則是variable。 假如變數為4, 在memory
→ clonsey1314: 裡則佔lg4=2, 但是程式執行次數實際上為4次(2^2)，
→ clonsey1314: 所以為指數成長
似懂非懂 我再想想 謝謝！！
推 awilliea: 我覺的課本應該是假設W比n大很多，大到我們根本沒辦法
→ awilliea: 用固定的bit數去表示，所以他才將W化成2^m，而n因為比
→ awilliea: 較小，可以用固定bit去表示，e.g. n=32k or n=64k，所以
→ awilliea: O(32k*2^m)=O(k*2^m)，n有沒有化成bit數並不影響整個時
→ awilliea: 間複雜度。
感覺比較像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
推 awilliea: https://stackoverflow.com/questions/19647658/what-is
→ awilliea: -pseudopolynomial-time-how-does-it-differ-from-polyn
→ awilliea: omial-time我是看這篇的，因為如果n指的是程式執行次數
→ awilliea: 而不用化成bit數的話，文章下面那個isPrime(n)時間複雜
→ awilliea: 度應該為O(n)（這個function只執行n-2次）
我的理解是 因為他這個n指的是數值 因為他判斷是不是質數
跟knapsack指的次數不一樣
※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 19:40:33
推 FRAXIS: #1N-azPo9 我以前回答過類似問題
我懂了 寫的超詳細 感謝！！！！！
※ 編輯: q1qip123 (180.217.227.170), 10/16/2017 20:38:37