The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack.

Why is this not a polynomial-time algorithm?

I have read that one needs $\lg W$ bits to represent $W$, so it is exponential time. But, I don't understand, one also needs $\lg n$ bits to represent $n$, doesn't one? So, for example, merge sort is not polynomial time, because its complexity is $O(n\lg n)$ and one needs $\lg n$ to represent $n$?

What am I missing here?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top