How to understand the knapsack problem is NP

 

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.)

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

    • 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=20, but the length is twice long:

    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.

    It all depends on which parameters you put inside O(...) .

    If target weight is limited by number W , then problem has O(n*W) complexity, as you mentioned.

    But if weights are way too big and you need algorithm with complexity independent of W , then problem is NP-complete. ( O(2^n*n) in most naive implementation).

    链接地址: http://www.djcxy.com/p/39972.html

    上一篇: 难的问题不是NP

    下一篇: 如何理解背包问题是NP