如何理解背包问题是NP完全问题？ [英] How to understand the knapsack problem is NP-complete?

问题描述

我们知道，背包问题可以在O（NW）复杂性动态规划来解决。但是，我们说这是一个NP完全问题。我觉得这是很难明白这里。

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是项数。W为最大音量。）

(n is the number of items. W is the maximum volume.)

推荐答案

诀窍是：O（NW）看起来像一个多项式时间，但它不是，它的伪多项式。 时间复杂度的算法需要为长度的位其输入功能的时间。动态编程解决方案确实是线性的单位为W，但指数在W的长度的价值 - 那是最重要的。

The trick is: O(nW) looks like a polynomial time, but it is not, it is pseudo-polynomial. Time complexity measures the time that an algorithm takes as 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 of W - and that's what matters.

更多参考：

• http://www.cs.ship.edu/~tbriggs/动态/ index.html的
• <一个href="https://web.archive.org/web/20100627162045/http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27" rel="nofollow">http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27

• 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

修改

对于背包问题的动态解决方案的时间复杂度基本上是由一个嵌套循环给出：

The time complexity of the dynamic solution for the Knapsack problem is basically given by a nested loop:

// 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）。什么意思线性增加了算法的输入的大小？这意味着使用逐渐变长的项目阵列（所以 N ， N + 1 ， N + 2 ，...），并逐渐变长W（所以如果W X 有点长，后一步，我们使用 X +1 位，则 X + 2 位，...）。但值的W的指数增长与 X ，这样的算法是不是真的多项式，它的指数（但它看起来是多项式，因此名称：伪多项式）

Thus, the time complexity is clearly O(nW). 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 longer W (so if W is x bit long, after one step we use x+1 bits, then x+2 bits, ...). But the value of W grows exponentially with x, thus the algorithm is not really polynomial, it's exponential (but it looks like it is polynomial, hence the name: pseudo-polynomial)

这篇关于如何理解背包问题是NP完全问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！