为什么要以n和2的W位数来说明背包问题的运行时间

Question

最近，由于post，我开始理解伪多项式的含义。但是，我的一个亟待解决的问题是，与动态编程一起使用时，背包问题为什么运行时间为，而不是。其中，n是要考虑的背包项目数，是编码W所需的位数，是给定x位数的可能状态（值）的数量。考虑到时间复杂度的正式定义将问题的大小定义为

问题输入的大小是位数写出该输入。

由于权重的位数不是固定的而是可变的，所以从0到W乘以值n或的所有可能值最多为个总位数。话虽如此，为什么与动态编程配对时背包的运行时具有而不是的运行时。我知道，但是时间复杂度将输入的大小称为位数。我正在做出什么假设，或者我缺少什么知识可以纠正这种脱节。

Answer 1

这里是与背包输入尺寸有关的说明。

• 项目数n可以用O（lg n）位表示；
• n项目权重：注意每个项目权重必须≤W（否则我们可以忽略那些权重大于W的项目），我们可以使用O（lg W）位，共O（n lg W）位；
• n项目值：让最大值为V。然后，可以使用O（lg V）位表示每个项目值，总共使用O（n lg V）位。

因此，总输入大小为O（lg n + n（lg W + lg V））= O（n（lg W + lg V））。

让b = lg W和v = lg V。然后，输入大小为O（n（b + v））。现在，请注意，动态编程解决方案v的O（nW）运行时间未明确显示，因此运行时间为O（nW）= O（ n2 ^ b）。