大家好
这里有一个观念想要请教各位版友
书本上说0-1背包问题的复杂度是O(nW)=O(n2^m)
m=lg W
这部分的解释真的看不太懂，希望可以请教各位
我的理解是因为W其实仅需lg W bits即可，而却需要处理W时间，所以相当于输入m，却花了2^m等级的时间
然而如果是这样我觉得不懂的是那为什么其他的问题没有这个状况呢？
其他问题我input n不也是只需要lg n bits就可以存了吗？那为什么其他问题不会有这个结论？
我猜我是对这个这个理解有误，希望版友可以解惑，谢谢！！

推这个问题，我只不知道为什么是m=lg W单纯看O(nW)是可以理解

W只是一个input 我猜化成m是有想要转换成问题大小的意味在转换成bit bit数就会变成问题大小啦图形算法 例如O(m) 是代表input真的有m个点 但是knapsack的W只是一个数字 并不是1,2,3...,W当成input输入进来

虽然是个数字但不也是要填n*W的矩阵吗我也觉得满奇怪的