Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]
题
This question already has an answer here:
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?
没有正确的解决方案
不隶属于 cs.stackexchange