如何理解背包问题是NP
我们知道背包问题可以通过动态规划解决O（nW）的复杂性。 但是我们说这是一个NP完全问题。 我觉得这里很难理解。
（n是项目的数量，W是最大音量。）
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指数增长，因此算法并不是真正的多项式，它是指数的（但它看起来像多项式，因此名称：“伪多项式”）。
更多参考
在背包0/1问题中，我们需要2个输入（1个数组和1个整数）来解决这个问题：
假设n = 10和W = 8：
所以时间复杂度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）= 0（10 * 128）= 0 （1280）
所需时间以指数术语增加，所以这是一个NPC问题。
这完全取决于你将哪些参数放在O(...) 。
如果目标权重受数W限制，则问题具有O(n*W)复杂性，正如您所提到的那样。
但是如果权重太大而且需要复杂度与W无关的算法，那么问题就是NP完全问题。 （ O(2^n*n)在最天真的实现中）。