0-1knapsack problem

今天上演算法的時候，老師解釋在dynamic programming的解法下，0-1knapsack 的 time complexity 為 O(nW)，而O(nW)是一個exponential的複雜度。

原因是因為我們估算複雜度的時候，無論是O(n)、O(n^2)、O(nlgn)…其中的n都表示input size，且還有一個要件是：
要估算時間複雜度，每一個program裡面的operation執行時間都是constant time
（你找的到一個constant c，使得所有operation time都<=c）

然而在背包問題用DP方式解的情形，時間複雜度為O(nW)。
在這裡n為可選擇的item的數量，也就是input size。
而關鍵的W代表的是背包可以負荷的重量上限，“它是一個值，而不是input size”。
（換句話說W輸入很大的時候，例如10億，他在電腦二進位的表示法中，最多占lg(10,000,000,000) 的 ceiling個bit，也就是30個bit。宣告一個int(假設一個int為32bit)存就存的下。）
也就是說W是