algorithm - 如何理解背包问题是NP完全的？

Question

我们知道背包问题可以通过动态规划以O(nW)的复杂度来解决。但是我们说这是一个NP完全问题。我觉得这里很难理解。

(n为元素数量，W为最大体积。)

Answer 1

O(n*W) 看起来像一个多项式时间，但它不是，它是pseudo-polynomial .

时间复杂度衡量算法所花费的时间作为其输入的长度(以位为单位) 的函数。动态规划解决方案确实W 的值是线性的，但W 的长度是指数级的——并且这才是最重要的!

更准确地说，背包问题的动态解决方案的时间复杂度基本上由嵌套循环给出:

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

因此，时间复杂度显然是O(n*W)。

线性增加算法输入的大小意味着什么？这意味着使用逐渐变长的项目数组(如 n、n+1、n+2、...)和逐渐变长的 W(因此，如果 W 的长度为 x 位，在一步之后我们使用 x+1 位，那么 x+2 位，...)。但是 W 的 value 随 x 呈指数增长，因此该算法并不是真正的多项式，它是指数的(但它看起来像多项式，因此得名:“伪多项式”)。

---

更多引用资料

• 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