How to understand the knapsack problem is NP-complete?
We know that the knapsack problem can be solved in O(nW) complexity by dynamic programming. But we say this is a NP-complete problem. I feel it is hard to understand here.
(n is the number of items. W is the maximum volume.)
Answer
O(n*W) looks like a polynomial time, but it is not, it is pseudo-polynomial.
Time complexity measures the time that an algorithm takes as a function of the length in bits of its input. The dynamic programming solution is indeed linear in the value of W, but exponential in the length of W — and that's what matters!
More precisely, the time complexity of the dynamic solution for the knapsack problem is basically given by a nested loop:
// here goes other stuff we don't care about
for (i = 1 to n)
for (j = 0 to W)
// here goes other stuff
Thus, the time complexity is clearly O(n*W).
What does it mean to increase linearly the size of the input of the algorithm? It means using progressively longer item arrays (so n, n+1, n+2, ...) and progressively longer W (so, if W is x bits long, after one step we use x+1 bits, then x+2 bits, ...). But the value of W grows exponentially with x, thus the algorithm is not really polynomial, it's exponential (but it looks like it is polynomial, hence the name: "pseudo-polynomial").