大家好
這裡有一個觀念想要請教各位版友
書本上說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的矩陣嗎我也覺得滿奇怪的