[問題] 0/1背包問題的時間複雜度
看板Prob_Solve (計算數學 Problem Solving)作者i78524 (Shulei)時間13年前 (2011/10/24 19:37)推噓2(2推 0噓 5→)留言7則, 5人參與討論串1/4 (看更多)
0/1背包問題的時間複雜度
雖然是演算法的問題，不過是想要和大家請教時間複雜度
想一想之後就決定po到這裡
請大家多多指教，謝謝！
我想問0/1背包問題的時間複雜度的問題
問題如圖 http://i.imgur.com/Sltc4.jpg
以下根據wiki百科
"
儘管背包問題的時間複雜度為O(nW)，但它仍然是一個NP完全問題。這是因為W同問題的輸
入大小並不成線性關係。原因在於問題的輸入大小僅僅取決於表達輸入所需的比特數。事
實上，log W，即表達W所需的比特數，同問題的輸入長度成線性關係。
"
wiki也是做類似的解釋
不過我還是不懂為什麼只有W要看成BIT數...
請高手解釋一下，謝謝大家了。
:::::::::::::::::::::::::::::::::::::::::::::::::::::::
我是今年資工所的考生，不過沒有補習了
所以問的這個問題也是完全偏向研所考題的
(如果有什麼適合研所考試問問題或互相討論的版也請告知一下)
如果不能在這邊問了話，我會自己刪除的...
謝謝大家，謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.21.235.246
→
10/24 19:38, , 1F
10/24 19:38, 1F
→
10/24 19:50, , 2F
10/24 19:50, 2F
→
10/24 19:50, , 3F
10/24 19:50, 3F
推
10/24 22:07, , 4F
10/24 22:07, 4F
推
10/25 08:16, , 5F
10/25 08:16, 5F
→
10/25 08:26, , 6F
10/25 08:26, 6F
→
10/25 15:17, , 7F
10/25 15:17, 7F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12