title: Why is the knapsack problem pseudo-polynomial?
body: <p>I know that <code>Knapsack</code> is NP-complete while it can be solved by DP. They say that the DP solution is <code>pseudo-polynomial</code>, 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 <code>pseudo-polynomial</code> thing to me slowly ?</p>