-
29-09-2020 - |
题
我的问题是为什么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。
我在这个问题上误解了什么?
谢谢。
解决方案
此处是如何对输入进行编码:
- 项目1的重量和值。
- 第2项的重量和价值。
- ...
- 项目 $ n $ 。
- $ w $ 。
假设权重和值是整数,最多是 $ m $ ,并且两者都以二进制编码为 $ w $ 。然后编码的长度是 $$ \ omega(n + \ log w),o(n \ log m + \ log w)。 $$ 希望这阐明了 $ n $ 和 $ w $ 。
之间的差异不隶属于 cs.stackexchange