作者i78524 (Shulei)
看板Prob_Solve
标题[问题] 0/1背包问题的时间复杂度
时间Mon Oct 24 19:37:01 2011
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
1F：→ firejox:0与1 选与不选呀... 10/24 19:38
2F：→ suhorng:我自己是觉得...因为W是输入的"数值"范围, 不是"数量"范围 10/24 19:50
3F：→ suhorng:但以上只是我自己的想法...我没修过课没念过... 10/24 19:50
4F：推 chchwy:Grad-ProbAsk版是你的好朋友 10/24 22:07
5F：推 DJWS:因为对W取log之後(log底数为二)，就是W二进位表示法的比特数 10/25 08:16
6F：→ DJWS:输入数值到Turing Machine里面 输入的是二进位数字 10/25 08:26
7F：→ i78524:谢谢大家！还有得到了Grad-ProbAsk的相关资讯真的很开心 :) 10/25 15:17