1
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ Is there a motivation for that particular example of the $B$ constraint? $\endgroup$ – Brian Hopkins Apr 21 at 15:43
  • $\begingroup$ I want to reduce this variation of knapsack problem to my own problem. $\endgroup$ – Eric Huang Apr 22 at 4:57
  • $\begingroup$ I change a little bit on the constraint. Hope that it may facilitate the problem reduction. $\endgroup$ – Eric Huang Apr 22 at 12:29
  • $\begingroup$ Do you have a typo in the sum index in your constraint restriction? You sum over $h$, but there is no $h$ in the sum. $\endgroup$ – Joel David Hamkins Apr 22 at 12:36
  • $\begingroup$ @JoelDavidHamkins Thanks for pointing it out. I have updated it. $\endgroup$ – Eric Huang Apr 22 at 14:00
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ That is a nice reduction. Sorry I made a mistake specifying the constraint. The correct constraint should $B<\sum_h w_h<2B$. I still wanna give you a vote for answering my question. Thanks. $\endgroup$ – Eric Huang Apr 22 at 14:59
  • $\begingroup$ I will be great if you could also know how to perform the reduction in my corrected constraint. $\endgroup$ – Eric Huang Apr 22 at 15:10
  • $\begingroup$ @EricHuang You should edit the question with the correct constraint then. Incidentally the same reduction still works as $\tilde{B} = B+W < 2W < 2B+2W = 2\tilde{B}$. $\endgroup$ – mlk Apr 23 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.