0-1没有重复的背包

Question

我的问题是为什么o（nw）在背包问题上是伪多项式。

我在stackoverflow中读了很多解释，但我真的不明白它。 （ https://stackoverflow.com/questions / 19647658 /什么是-Pseudopolynomial-time-de-de-dif-It-Inf-polynomial-time ， https://stackoverflow.com/questions/4538581/why-是-Knapsack-stricion-pseudo-polymomial＃ack-4538668 ）

核心的事情是为什么我们必须只认为'w'是'logw'的比特输入，而不是'n'是'log n'bits。

许多解释说，“W”是整数，但'n'只是项目的数量。因此，只有'W'大小与“logw”成比例。

我认为这个逻辑必须应用于'n'。

假设我们将项目编号为1到n，用于区分项目，

我们必须将数字从1到n计数。

我认为循环对w次迭代是相同的。

因此，我认为它与'w'相同，因为这个计数也需要'log n'bits。

我在这个问题上误解了什么？

谢谢。

Answer 1

此处是如何对输入进行编码：

• 项目1的重量和值。
• 第2项的重量和价值。
• ...
• 项目 $ n $ 。
• $ w $ 。

假设权重和值是整数，最多是 $ m $ ，并且两者都以二进制编码为 $ w $ 。然后编码的长度是 $$ \ omega（n + \ log w），o（n \ log m + \ log w）。 $$ 希望这阐明了 $ n $ 和 $ w $ 。

之间的差异