logo标签列表

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

algorithmcomplexity-theory
95
我们知道背包问题可以通过动态规划在O(nW)的时间复杂度内得到解决。但是我们称这是一个NP完全问题。我感觉这里很难理解。（n代表物品数量，W代表最大容量）
这个Quora回答使用了一个例子，展示了非常清晰的推理过程，让你理解伪多项式时间复杂度这个概念，并了解背包问题如何在伪多项式时间内运行。 - DanSkeel
7个回答
59

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+1位，然后是x+2位，...）。 但是，W的值随着x呈指数级增长，因此该算法实际上不是多项式函数，而是指数函数（但它看起来像是多项式函数，因此得名“伪多项式”）。

进一步参考资料

2
有两种方法来衡量数字的大小。给定数字10和1000，你可以说1000要么是两倍大（字符数量），要么是一百倍大。由于差异是指数级别的，因此你可以有一个算法，它在数值大小方面是多项式测量的，在位数方面是指数测量的。 - David Thornley
9
我认为编码中的比特数与这个问题完全没有关系。我确实理解比特数量如何影响整数分解的复杂性，因为单个整数是“输入”。但是，在这里，数字W和n代表的是循环迭代次数。您可以以任何方式对它们进行编码，那个循环仍将迭代n*W次。我认为之所以称其为“伪多项式”，是因为n是实际的输入大小，而W可以比n大得多，因此不能公平地视为常数。 - The111
4
为了让您理解，__1)__可以考虑一个从1到n（其中n是输入的值）的for循环；在这种情况下，当循环执行10^12次时，输入的大小仍然约为40位。迭代次数增长的速度比编码输入所需的位数快。时间复杂度 不是 线性的。__2)__同样地，考虑一个for循环，它遍历一个大小为n的输入数组，从1到n进行迭代；如果你有10^12次迭代，那么意味着你的数组包含10^12个项目。迭代次数与输入大小以相同的速度增长。时间复杂度是线性的。 - Zsolt Safrany
4
如果我们考虑我的例子，那么让我们在输入中添加一个额外的比特。这样一来，我们会使迭代次数加倍（增加10^12次迭代），但输入的长度仅增加了1个比特。而下一个额外的比特将带来更多的额外迭代次数。因此，“迭代次数增长的速度要快于编码输入所需的比特数”，其中输入表示迭代次数。明白了吗？ :-) - Zsolt Safrany
2
让我恍然大悟的是，对于背包问题输入而言，n不是一个数字，而是实际的物品，而W则是一个数字。你不能解决重量为10、物品数量为6的背包问题。你实际上需要将n表示为物品的数组...一个增长的数组。我们用一个数字来表示n（一组物品）的大小，但用位来表示W（一个数字）的大小。 - amoffat
显示剩余8条评论
37
在背包0/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）= O（20 * 8）= O（160）
但是，当你将W的大小加倍时，它并不意味着W = 16，而是长度将增加一倍：
W = 1000 -> W =二进制术语下的10000000（8位长）
因此，T（n）= O（nW）= O（10 * 128）= O（1280）
所需的时间以指数项增加，因此它是一个NPC问题。
1
谢谢YoEugene，我终于有点明白了！所以这里的重点是复杂度与输入大小呈指数关系，而在这种情况下，输入大小是W的位长度。当我们讨论检查一个数N是否为质数时，同样的事情发生了，输入实际上是N的位长度，因此尽管需要N步和O(N)的复杂度，但它仍然是伪多项式。相反，如果我们想在长度为N的数组中查找一个数字，则输入实际上是N，因此O(N)的复杂度实际上是线性的。 - yeelan
7

一切取决于您在 O(...) 中放入哪些参数。

如果目标重量受数字 W 的限制，则问题的复杂度为 O(n*W)，就像您所提到的那样。

但是，如果重量过大，并且您需要具有与 W 无关的复杂度的算法，则问题是 NP 完全问题。 （在最朴素的实现中，复杂度为 O(2^n*n)）。

其他动态规划问题怎么样呢？例如，最长公共子序列问题可以在O（L_1 * L_2）的时间内解决。我们能否说它不是多项式的？ - cnhk
@cnhk 看起来它具有多项式复杂度，O(n^2)。但是有各种各样的DP算法，例如那些在给定集合的所有子集上工作的算法（2^n个组合），因此我不会说每个DP问题都可以在多项式时间内解决。 - Nikita Rybak
6
输入的大小是权重的log(W)位（对于“值”和“重量”数组为O(n)）。
因此，权重的输入大小为j = log(W)（而不仅仅是W）。 因此，W = 2ʲ（使用二进制）。
最终复杂度为O(n * W)

这个O(n * W)可以重写为O(n * 2ʲ)，其与输入大小的指数相关。

因此，该解决方案不是多项式的。
4
0
-1
要理解NP完备性，您需要学习一些复杂性理论。然而，基本上，它是NP完全的，因为对于背包问题的有效算法也将是SAT、TSP和其他问题的有效算法。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接