如何理解背包问题是NP完全问题？
我们知道背包问题可以通过动态规划以 O(nW) 复杂度解决。但我们说这是一个NP完全问题。我感觉这里很难理解。
（n 是物品数量。W 是最大体积。）
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.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
O(n*W)看起来像一个多项式时间，但它不是，它是伪多项式。时间复杂度衡量算法所花费的时间，作为其输入位长度的函数。动态规划解决方案确实与
W的值呈线性关系，但与W的长度呈指数关系 - 并且这才是最重要的！更准确地说，背包问题动态求解的时间复杂度基本上由嵌套循环给出：
因此，时间复杂度显然是
O(n*W)。线性增加算法输入的大小意味着什么？这意味着使用逐渐更长的项目数组（例如
n、n+1、n+2...）和逐渐更长的W（因此，如果W的长度为x位，在一步之后我们使用x+1位，则x+2位，...）。但是W的值随着x呈指数增长，因此该算法并不是真正的多项式，而是指数的（但看起来像是多项式，因此得名：“伪多项式”）。更多参考文献
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 ofW— 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:
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 longerW(so, ifWisxbits long, after one step we usex+1bits, thenx+2bits, ...). But the value ofWgrows exponentially withx, thus the algorithm is not really polynomial, it's exponential (but it looks like it is polynomial, hence the name: "pseudo-polynomial").Further References
在背包 0/1 问题中，我们需要 2 个输入（1 个数组和 1 个整数）来解决这个问题：
让我们假设 n=10 且 W=8：
所以时间复杂度 T(n) = O(nW) = O(10*8) = O(80)
如果你将 n 的大小加倍< /strong>:
n = [n1, n2, n3, ... , n10] -> n = [n1, n2, n3, ... , n20]
所以时间复杂度 T(n) = O(nW) = O(20*8) = O(160)
但当你 < strong>W的大小增加一倍，并不是说W=16，而是长度会变长一倍：
W = 1000 -> W = 10000000（二进制形式）（8 位长），
因此 T(n) = O(nW) = O(10*128) = O(1280)
时间需要以指数形式增加，所以这是一个 NPC 问题。
In knapsack 0/1 problem, we need 2 inputs(1 array & 1 integer) to solve this problem:
Let's assume n=10 and W=8:
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.
这完全取决于您在
O(...)中放入哪些参数。如果目标权重受数字
W限制，则问题的复杂度为O(n*W)，正如您提到的。但如果权重太大并且您需要复杂度与 W 无关的算法，那么问题就是 NP 完全问题。 （在大多数简单的实现中，
O(2^n*n)）。It all depends on which parameters you put inside
O(...).If target weight is limited by number
W, then problem hasO(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).输入的大小为权重的
log(W)位（对于“value”和“weight”数组，输入的大小为O(n)）。因此，权重的输入大小为
size = log(W)（而不仅仅是W）。因此，W = 2size文本（使用二进制）。最终复杂度为
O(n * W)所以，这个解不是多项式。
The size of input is
log(W)bits for the weight (andO(n)for "value" and "weight" arrays).So, the input size of weight is
size = log(W)(and not mereW). So,W = 2sizetext (as binary is used).The final complexity is
O(n * W)So, this solution is not polynomial.
这是因为背包问题具有伪多项式解，因此被称为弱 NP-Complete （而不是强 NP 完全）。
This is because the knapsack problem has a pseudo-polynomial solution and is thus called weakly NP-Complete (and not strongly NP-Complete).
您可以阅读这个简短的解释：Knapsack 的 NP 完备性。
You can read this short explanation: The NP-Completeness of Knapsack.
要理解 NP 完整性，您必须学习一些复杂性理论。然而，基本上，它是 NP 完全的，因为背包问题的有效算法也是 SAT 的有效算法、TSP 以及其余的。
To understand NP-completeness, you have to learn a bit of complexity theory. However, basically, it's NP-complete because an efficient algorithm for the knapsack problem would also be an efficient algorithm for SAT, TSP and the rest.