Knapsack problem with capacity constraint

Question

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 the capacity such that $\sum_{h=1}^i w_h <B< \sum_{h=1}^i 2w_h$? Is it still Np-hard under this constraint?

Answer 1

I assume that your constraint should read $\sum_{h=1}^i p_h w_h < B < 2 \sum_{h=1}^i p_h w_h$, not $\sum_{h=1}^i w_h < B$ otherwise the trivial solution $p_h \equiv 1$ always applies.

There is an reduction by adding a very heavy and expensive item. Take any Knapsack problem like you stated. Calculate $W := \sum_h w_h$, $V:= \sum_h v_h$. We can assume that $0 < B < W$, otherwise the solution is trivial. Now add another item with $w_{i+1} := W$ and $v_{i+1} := V+1$ and use a new capacity $\tilde{B} := B+W$. The new problem is obviously polynomial in size wrt. to the old one.

Now any Knappsack solution to this new problem has to include item $i+1$, as taking only this item is already better than ignoring it and taking all of the others. This means that you can take an optimal Knapsack solution to the new problem, remove this item and get an optimal Knapsack solution to the old one and vice versa. But since $\tilde{B} < 2W = 2w_{i+1}$, any optimal solution to the new problem also automatically satisfies your constraint.