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

看板Grad-ProbAsk作者shortid (我是短哀低)時間9年前 (2016/10/09 15:53)推噓3(3推 0噓 7→)

留言10則, 3人參與討論串1/3 (看更多)

大家好這裡有一個觀念想要請教各位版友書本上說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

10/09 16:37, , 1^F

10/09 16:37, 1^F

→

a19930301

10/09 16:37, , 2^F

10/09 16:37, 2^F

推

kyuudonut

10/09 18:19, , 3^F

10/09 18:19, 3^F