作者:
NTUmaki (西木野真姬)
2020-09-06 15:15:36版上兩篇文章看過了，但有些還是不懂、想確認
我目前理解是這樣：
0/1 knapsack problem 複雜度 O(nW)
n是物品數量（陣列有多少個‘’元素‘）
W就是一個數值（input 只會看到一個東西）
但數值跟物品數量都是人的定義，對電腦來說最後都是開了nW的二維陣列，算了nW格的東西。所以其實數值、數量對電腦程式來說沒差吧？
所以不太懂要取 m=lgW 然後說複雜度是O(n2^m) 的理由
目前我是這樣理解：
因為複雜度理論也是人定義的，所以當初我們要求的input 必須是一個可以數有多少個的東西，以此題來說，input就會真的出現n+1數字（n個價格、1個重量）
W我們沒辦法說他 size 是1，要找一個會隨著W變大而增長的東西當input size，所以取 bit 數當他的size
這邊再提一個疑問，如果我是取他有幾位數可以嗎？（取log 10為底，反正出來的是exponential）
作者:
aarzbrv (我愛鑽石光! 芒! 長!~~)
2020-09-06 15:59:00「我是取他有幾位數可以嗎？」的回答，就是您所理解到的「所以取bit 數當他的size」。會不會是因為還沒發明電腦的社會習慣用log 10，發明後用log 2，造成您的困惑呢？
作者:
NTUmaki (西木野真姬)
2020-09-06 16:11:00不算困擾，只是想說關鍵應該是要把W的size量化成 隨著W這個數字越大，他的size也要越大，所以取他有幾位也對吧
作者:
aarzbrv (我愛鑽石光! 芒! 長!~~)
2020-09-06 16:21:00或是「取他有幾位(元)」，您是否認同在下多加一個字呢？
作者:
NTUmaki (西木野真姬)
2020-09-06 16:22:00原本的我同意啊，只是我想說取幾位表達趨勢 也是exponential
作者:
aarzbrv (我愛鑽石光! 芒! 長!~~)
2020-09-06 16:27:00您目前的主文與推文，在下如果沒會錯意的話，都同意；希望在下的推文沒有誤導您的地方，抱歉！
作者:
NTUmaki (西木野真姬)
2020-09-06 20:54:00不會不會 感謝回覆
作者:
FRAXIS (喔喔)
2020-09-06 22:20:00主要是執行時間跟 W 有關，所以才要討論 bit。像是 comparison-based 的 sorting 都是假設 comparison是 O(1) 時間 與 bit 無關，所以就不用討論 bit。但是你也可以定義 comparison 跟 bit 長度有關的計算模型只是教科書上不太會這樣介紹..