[理工] 演算法 0-1knapscak觀念疑問

[shortid (我是短哀低)]

大家好

這裡有一個觀念想要請教各位版友

書本上說0-1背包問題的複雜度是O(nW)=O(n2^m)
m=lg W
這部分的解釋真的看不太懂，希望可以請教各位

我的理解是因為W其實僅需lg W bits即可，而卻需要處理W時間，所以相當於輸入m，卻花了2^m等級的時間

然而如果是這樣我覺得不懂的是那為什麼其他的問題沒有這個狀況呢？
其他問題我input n不也是只需要lg n bits就可以存了嗎？那為什麼其他問題不會有這個結論？

我猜我是對這個這個理解有誤，希望版友可以解惑，謝謝！！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.88.231
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1475999630.A.D41.html
推 a19930301: 推這個問題，我只不知道為什麼是m=lg W
→ a19930301: 單純看O(nW)是可以理解
推 kyuudonut: W只是一個input 我猜化成m是有想要轉換成問題大小的
→ kyuudonut: 意味在
→ kyuudonut: 轉換成bit bit數就會變成問題大小啦
→ kyuudonut: 圖形演算法 例如O(m) 是代表input真的有m個點 但是kn
→ kyuudonut: apsack的W只是一個數字 並不是1,2,3...,W當成input輸
→ kyuudonut: 入進來
推 hopward: 雖然是個數字但不也是要填n*W的矩陣嗎
→ hopward: 我也覺得滿奇怪的