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

我们知道背包问题可以通过dynamic规划解决O（nW）的复杂性。 但是我们说这是一个NP完全问题。 我觉得这里很难理解。

（n是项目数量，W是最大音量）

Answer 1

诀窍是：O（nW）看起来像一个多项式时间，但它不是，它是伪多项式 。 时间复杂度衡量一个algorithm作为其input位长的函数的时间。 dynamic规划解决scheme在W的值上确实是线性的，但在W的长度上是指数的 – 这是重要的。

进一步参考：

• 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

编辑

背包问题的dynamic解决scheme的时间复杂度基本上是由一个嵌套的循环给出的：

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

因此，时间复杂度显然是O（nW）。 这是什么意思，以增加线性的algorithminput的大小？ 这意味着使用逐渐更长的项目数组（所以n ， n+1 ， n+2 ，…）和逐渐更长的W（所以如果W是x位长，一步之后我们使用x+1位，那么x+2位，…）。 但是W的值随着x指数增长，因此algorithm并不是真正的多项式，它是指数的（但看起来它是多项式的，因此名称：伪多项式）

Answer 2

在背包0/1问题中，我们需要2个input（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）= 0（20 * 8）= 0（160）

---

但是，如果W是W的两倍，那么并不意味着W = 20，而是长度是两倍：

W = 1000 – > W = 10000000二进制（8位长）

所以T（n）= O（nW）= 0（10 * 128）= 0 （1280）

所需时间以指数术语增加，所以这是一个NPC问题。

Answer 3

这完全取决于你把哪个参数放在O(...) 。

如果目标权重受数W限制，则问题具有O(n*W)复杂性，正如你所提到的那样。

但是如果权重太大，并且需要复杂度不依赖于Walgorithm，那么问题是NP完全的。 （ O(2^n*n)在最天真的实现）。

Answer 4

非常好的问题！ 很容易混淆。 这是因为背包问题有一个伪多项式解，因此称为弱NP完全 ，而不是强NP-Complete 。

• http://en.wikipedia.org/wiki/Weakly_NP-complete

在这里看到相关的post

• 为什么背包问题是伪多项式？

希望这可以帮助！

Answer 5

input的大小是权重的log W比特（以及值和权重arrays的O（n））。因此，权重的input大小是

 i = log W ( and not mere W ) So, W = 2^i ( as binary is used ) 

由于最终的复杂度是O（n * W），所以可以重写为

 O(n * 2^i) ( making it exponential in the size of input ) 

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

Answer 6

你可以阅读这个简短的解释： http : //www.derf.net/knapsack/#KnapNP （背包的NP-Completeness）我希望它能帮助你

Answer 7

要理解NP完整性 ，你必须学习一点复杂性理论：你不会从这个理论中得到这个理论！ 然而，基本上，这是NP完全的，因为一个有效的algorithm的背包问题也将是一个有效的algorithmSAT ， TSP等。

正如@Nikita所指出的那样，有限的目标权重版本不在NP中，而是在P中。这​​个版本不能用来解决任何NP完全问题（高效）。