The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w\_1,w\_2,...,w\_i$, positive values $v\_1,v\_2,...,v\_i$, and a bag with capacity $B$, we want to insert items into the bag without exceeding the capacity $B$ while maximising the total values (i.e., maximising $\sum\_{h=1}^i p\_h\*v\_h$ subject to (1) $p\_h=0$ or 1, (2) $\sum\_{h=1}^i p\_h\*w\_h \leq B$ ). I know the decision problem of knapsack problem is NP-complete and thus the optimisation version is NP-hard.


But what if we have the constraint restricting each item value $v\_h$ within the range $[0,w\_h]$? Is it still Np-hard under this constraint?



Knapsack problem with value range constraint
It is easy to enforce this constraint for a generic knapsack problem.
Indeed, it is enough just to multiply all $w\_h$ and $B$ by $c:=\max\_h \frac{v\_h}{w\_h}$. Then for any $h$,
$$v\_h = \frac{v\_h}{w\_h} w\_h\leq cw\_h,$$
i.e. $v\_h\in[0,cw\_h]$, while the constraint $
\sum\_h p\_hw\_h\leq B$ is equivalent to $\sum\_h p\_h(cw\_h)\leq cB$.


