I know that

`Knapsack`

is NP-complete while it can be solved by DP. They say that the DP solution is`pseudo-polynomial`

, since it is exponential in the “length of input” (i.e. the numbers of bits required to encode the input). Unfortunately I did not get it. Can anybody explain that`pseudo-polynomial`

thing to me slowly ?

**Answer**

The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it *pseudo*-polynomial.

Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the computational runtime uses the factor 1,000,000,000,000 which is O(2^{40}).

So the runtime is more accurately said to be O(N.2^{bits in W}), which is exponential.

Also see:

**Attribution***Source : Link , Question Author : Michael , Answer Author : Community*