背包问题为什么是伪多项式? [英] Why is the knapsack problem pseudo-polynomial?

问题描述

我知道Knapsack是NP完全的，而DP可以解决它.他们说DP解决方案是pseudo-polynomial，因为它在输入长度"(即，对输入进行编码所需的位数)中呈指数形式.不幸的是我没有得到.有人可以慢慢向我解释pseudo-polynomial的事情吗?

I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits required to encode the input). Unfortunately I did not get it. Can anybody explain that pseudo-polynomial thing to me slowly ?

推荐答案

对于具有N个项目且尺寸为W的背包的无界背包问题，运行时间为O(NW).尽管输入长度不是W，但W并非多项式，这就是使它成为 pseudo -多项式的原因.

The running time is O(NW) for an unbounded knapsack problem with N items and knapsack of size W. W is not polynomial in the length of the input though, which is what makes it pseudo-polynomial.

考虑W = 1,000,000,000,000.只需40位即可表示该数字，因此输入大小= 40，但是计算运行时使用的因子为1,000,000,000,000，即O(2 ⁴⁰ ).

Consider W = 1,000,000,000,000. It only takes 40 bits to represent this number, so input size = 40, but the computational runtime uses the factor 1,000,000,000,000 which is O(2⁴⁰).

因此，运行时间更准确地说是O(W中的N.2 ^位)，这是指数的.

So the runtime is more accurately said to be O(N.2^{bits in W}), which is exponential.

另请参阅:

• 如何理解背包问题是NP完全的?
• 背包的NP完全性
• 用于0-1的动态编程算法的复杂性背包问题
• 伪多项式时间

• How to understand the knapsack problem is NP-complete?
• The NP-Completeness of Knapsack
• Complexity of dynamic programming algorithm for the 0-1 knapsack problem
• Pseudo-polynomial time

这篇关于背包问题为什么是伪多项式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！