Knapsack problems are easily solved by dynamic programming. Dynamic programming runs in polynomial time; that is why we do it, right?
I have read it is actually an NP-complete problem, though, which would mean that solving the problem in polynomial problem is probably impossible.
Where is my mistake?
Knapsack problem is $\sf{NP\text{-}complete}$ when the numbers are given as binary numbers. In this case, the dynamic programming will take exponentially many steps (in the size of the input, i.e. the number of bits in the input) to finish $\dagger$.
On the other hand, if the numbers in the input are given in unary, the dynamic programming will work in polynomial time (in the size of the input).
This kind of problems is called weakly $\sf{NP\text{-}complete}$.
$\dagger$: Another good example to understand the importance of the encoding used to give the input is considering the usual algorithms to see if a number is prime that go from $2$ up to $\sqrt{n}$ and check if any of them divide $n$. This is polynomial in $n$ but not necessarily in the input size. If $n$ is given in binary, the size of input is $\lg n$ and the algorithm runs in time $O(\sqrt{n}) = O(2^{\lg n/2})$ which is exponential in the input size. And the usual computational complexity of a problem is w.r.t. the size of the input.
This kind of algorithm, i.e. polynomial in the largest number that is part of the input, but exponential in the input length is called pseudo-polynomial.
m (pack size) and n (num of items) is totally unknown, right? And re "when the numbers are given as binary numbers"... but couldn't you say that for anything? With most algorithms, we talk about input size in base 10. Why talk about binary here? And whether you encode in binary, octal, decimal, etc... the actual number of times you iterate through your main algorithm loop is directly dependent on both n and W.
$\endgroup$
The main confusion lies in the difference between "size" and "value".
"Polynomial Time" implies polynomial w.r.t the size of input.
"Pseudopolynomial Time" implies polynomial w.r.t the value of the input. It can be shown (below) that this is equivalent to being exponential w.r.t the size of the input.
In other words: Let $N_{size}$ represent the size of the input and $N_{val}$ represent the value of the input.
Polynomial Time: $O(N_{size}^x)$ for $x\in\mathbb{N}$
Pseudopoly. Time: $O(N_{val}^x)$ for $x\in\mathbb{N}$
Now, the knapsack problem has a pseudopolynomial, not polynomial, solution because the dynamic programming solution gives a running time dependent on a value -- i.e. $O(nW)$, where $W$ is a value representing the max capacity.
Now, a value can be converted into a size by representing it in terms of # of digits it takes to represent it. $N_{size}=Log_b(N_{val})$ tells you how many digits are needed to represent $N_{val}$ using base $b$. This can be solved for $N_{val}$ to give:
$$N_{val}=b^{N_{size}}$$
Plugging this into the pseudopolynomial time definition shows that it is exponential w.r.t $N_{size}$:
Pseudopoly. Time: $O(b^{xN_{size}})$ for $b, x\in\mathbb{N}$
The Knapsack problem as defined in Karp's paper is NP-Complete since there is a reduction from other NPC problem (Exact Cover, in this case) to Knapsack. This means that there is no polynomial algorithm that can solve all instances of the Knapsack problem, unless $\text{P}=\text{NP}$.
There are, however, different variants (e.g., 0-1 Knapsack and others) that may or may not have polynomial-time solutions or good approximations. But this is not the same as the general Knapsack problem. Also, there might be efficient algorithms that work for specific (families of) instances, but these algorithms will take longer on other instances.
