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

Question

我很难理解为什么使用动态规划的 0/1 背包不是多项式时间可解的。类似的问题被问到here。 Why is the knapsack problem pseudo-polynomial? .有人给出了解释，但我仍然不明白为什么我们要考虑权重输入的二进制表示。 n 怎么样，如果它以二进制表示形式考虑，我可以说它是项目数量的指数吗？同样，对于任何其他多项式时间算法，我可以声称它们具有指数时间复杂度，因为每个输入在计算机中都以二进制数字表示。我知道我错了。有人可以用简单易懂的方式指出原因吗？提前致谢。

Answer 1

一种非常简单的思考方式是，如果将限制加倍，输入的大小只会增加一位(因为限制是输入的一部分)，而运行时间会加倍。这显然是关于输入大小的指数行为。

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