Knap sack: Dynamic Programming

55 Views Asked by At

We are given the knapsack problem, such that the user can only carry weight $W$ and no. of items available is $n$.

Note: We cannot split the items which means cannot take 1.5 of item 1 for example.

The textbook says...

Using dynamic programming the problem can be solved in $\mathcal{O}(nW)$ time, which is reasonable when $W$ is small, but is not polynomial since the input size is $\propto log\ W$ rather than $W$.

My question is why is the input size proportional to $log\ W$ instead of $W$.