我们知道背包问题可以通过动态规划以O(nW)的复杂度来解决。但是我们说这是一个NP完全问题。我觉得这里很难理解。
(n为元素数量，W为最大体积。)
最佳答案
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 呈指数增长，因此该算法并不是真正的多项式，它是指数的(但它看起来像多项式，因此得名:“伪多项式”)。
更多引用资料
关于algorithm - 如何理解背包问题是NP完全的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3907545/