why is knapsack not polynomial?
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. ... So the runtime is more accurately said to be O(N. 2bits in W), which is exponential.