How to understand the knapsack problem is NP-complete?
Solution 1:
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").
Further References
- http://www.cs.ship.edu/~tbriggs/dynamic/index.html
- http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27
Solution 2:
In knapsack 0/1 problem, we need 2 inputs(1 array & 1 integer) to solve this problem:
- a array of n items: [n1, n2, n3, ... ], each item with its value index and weight index.
- integer W as maximum acceptable weight
Let's assume n=10 and W=8:
- n = [n1, n2, n3, ... , n10]
- W = 1000 in binary term (4-bit long)
so the time complexity T(n) = O(nW) = O(10*8) = O(80)
If you double the size of n:
n = [n1, n2, n3, ... , n10] -> n = [n1, n2, n3, ... , n20]
so time complexity T(n) = O(nW) = O(20*8) = O(160)
but as you double the size of W, it does not mean W=16, but the length will be twice longer:
W = 1000 -> W = 10000000 in binary term (8-bit long)
so T(n) = O(nW) = O(10*128) = O(1280)
the time needed increases in exponential term, so it's a NPC problem.