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

Question

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

(n是项目数.W是最大音量.)

Answer 1

O(n*W)看起来像一个多项式时间,但它不是,它是伪多项式.

时间复杂度测量算法作为其输入的位长度的函数所花费的时间.动态编程解决方案的价值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增长呈指数级增长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

Answer 2

在背包0/1问题中,我们需要2个输入(1个数组和1个整数)来解决这个问题:

1. n个项目的数组:[n1,n2,n3,...],每个项目都有其值索引和权重索引.
2. 整数W作为可接受的最大重量

假设n = 10且W = 8:

1. n = [n1,n2,n3,...,n10]
2. 二进制项W = 1000 (4位长)

所以时间复杂度T(n)= O(nW)= O(10*8)= O(80)

如果你加倍n的大小:

n = [n1,n2,n3,...,n10 ] - > n = [n1,n2,n3,...,n20 ]

所以时间复杂度T(n)= O(nW)= O(20*8)= O(160)

但是当你把W的大小加倍时,它并不意味着W = 20,但长度是两倍长:

W = 1000 - > W = 10000000二进制项(8位长)

所以T(n)= O(nW)= O(10*128)= O(1280)

所需的时间以指数项增加,因此这是一个NPC问题.

Answer 3

这一切都取决于你放在哪个参数O(...).

如果目标权重受数量限制W,那么问题O(n*W)就像你提到的那样复杂.

但是如果权重太大而你需要复杂性独立的算法W,那么问题就是NP完全.(O(2^n*n)在最天真的实施中).

Answer 4

输入的大小是log(W)权重的位（以及O(n)“值”和“权重”数组）。

\n\n

因此，权重的输入大小为j = log(W)（而不仅仅是W）。所以，W = 2\xca\xb2（使用二进制时）。

\n\n

最终复杂度为O(n * W)

\n\n

\n

这O(n * W)可以重写为O(n * 2\xca\xb2)，它与输入的大小呈指数关系。

\n

\n\n

所以，这个解不是多项式。

\n