为什么使用动态规划的0/1背包问题不是多项式时间算法

Question

我很难理解为什么使用动态规划的0/1背包问题不是多项式时间可解的。类似的问题已经在这里提出了。 为什么背包问题是伪多项式？ 有人给出了解释，但我仍然不明白为什么我们应该考虑将重量输入表示为二进制。如果考虑n的二进制表示，那么它是否可以说是与物品数量呈指数关系？同样地，对于任何其他多项式时间算法，我都可以声称它们具有指数时间复杂度，因为计算机中的每个输入都用二进制数字表示。我知道我错了。有人能以易于理解的方式指出为什么吗？谢谢。

- Christopher

---

这取决于对象数量和限制值的大小，这就是所谓的准多项式算法。您可以在此处找到详细解释：http://en.wikipedia.org/wiki/Time_complexity 。 - Igor Chornous

@kids_fox 那应该就是一个答案。 - Yuck

我认为你会发现你的观点“对于其他多项式时间算法，我可以声称它们具有指数时间复杂度”是错误的。如果你看到一个算法，只有当输入以一元方式给出时其运行时间才是多项式级别的，那么这是一个伪多项式时间算法，没有任何可靠的来源会将其描述为多项式时间算法。 - han

Answer 1

一个非常简单的思考方式是，如果你将限制加倍，输入的大小只会增加一位（因为限制是输入的一部分），而运行时间会加倍。这显然是与输入大小呈指数关系的行为。

然而，尽管加倍了项目数量也会使运行时间加倍，但它也会使输入项的大小加倍，因此输入大小和运行时间之间的这部分关系只是线性的。

- hammar

---

输入的大小仅增加了一个比特（因为限制是输入的一部分）。我不知道为什么输入的大小没有翻倍。 - Christopher

@Edward：因为 W 是用二进制编码表示的。如果它是用一元编码表示的话，那么它将是多项式。 - amit

Answer 2

给定以下输入的背包问题：n个物品价值v_i，n个重量w_i和一个容量K值（由k位表示），我们有：

输入大小为N = 2n * 64 + k位。

因此，背包DP解决方案的比特复杂度为O(N) = O(n * 2^k)（忽略常数因子64）

上述计算中隐含了以下假设： 每个重量w_i和每个价值v_i都可以用最大为8字节或64位的单词表示。

进一步阐述如下：

如果容量加倍（K' = 2K或k'=k+1），则输入仍包含n个值v_i，n个重量w_i和容量值K'（由k+1位表示）。因此，位数为N'=2n*64+k+1=N+1。总之，当k增加1时，位操作次数翻倍=> O(N)相对于k是指数级别的，相对于K是伪多项式级别的

如果物品数量加倍（n'=2n），则输入现在包含2n个物品价值v_i，2n个重量w_i和容量值K。因此，位数为N'=2*2n*64+k。总之，当n加倍时，位操作次数翻倍=> O(N)相对于n是多项式级别的

有关位复杂度和字复杂度的参考资料：

http://en.wikipedia.org/wiki/Context_of_computational_complexity

Book: A Programmer's Companion to Algorithm Analysis - Section 2.2

- Kristin