0-1 knapsack without repetition

Question

My question is why O(nW) at the knapsack problem is pseudo-polynomial.

I read lots of the explanation at stackoverflow, But I don't really understand it. (https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time, https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668)

The core thing is why we have to think only 'W' as 'logW' bits input, not 'n' as 'log n' bits.

The many explanation said that 'W' is integer but 'n' is just the number of item. Therefore only 'W' size is proportional to 'logW'.

I think this logic have to be applied to 'n'.

Assuming that we are numbering the items from 1 to n, for differentiating the items,

we have to count the numbers from 1 to n.

I think it is the same that the loop does iteration for W times.

Therefore I think it is same with 'W' because this counting also need 'log n' bits.

What do I mis-understand at this problem?

Thanks.

Answer 1

Here is how you encode the input:

• Weight and value of item 1.
• Weight and value of item 2.
• ...
• Weight and value of item $n$.
• $W$.

Suppose that the weight and value are integers, are at most $M$, and both are encoded in binary, as is $W$. Then the length of the encoding is $$ \Omega(n + \log W), O(n\log M + \log W). $$ Hopefully this clarifies the difference between $n$ and $W$.