The 0-1 knapsack problem is given by
$$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P1}\\& \text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$
Running the dynamic programming algorithm for this problem would give an optimal solution in $O(nW)$.
If I define $p_i=w_i/W$, I get the following knapsack problem:
$$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P2}\\& \text{subject to } \sum_{i=1}^n p_i x_i \leq 1,\\&\text{and } x_i \in \{0,1\}.\end{align}$$
Running the dynamic programming algorithm for this problem would give an optimal solution in $O(n)$. This is not true, isn't it?
1 Answer 1
The running time is $O(nW)$ if all weights are integers. This is because the dynamic programming table is indexed by possible weights of subsets. If all weights are integers, then since we are only interested in subsets whose sum of weights is at most $W$, there are only $W+1$ weights of subsets that could possibly interest us. This is where the $W$ factor in the running time is coming from.
Dividing all weights by $W$ accomplishes exactly nothing. You haven't changed the problem, so the required time for solving it is remains exactly the same.