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 each item value $v_h$ within the range $[0,w_h]$? Is it still Np-hard under this constraint?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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$.

Improve this answer
$\endgroup$
14
  • $\begingroup$ So is my problem just a special case of the generic knapsack problem you formulated with c=1? If so, it may not be sufficient to prove the NP-hardness of my knapsack problem. Is it correct? $\endgroup$
    – Rise of Kingdom
    Commented Apr 19, 2021 at 9:07
  • 1
    $\begingroup$ Vice versa, generic knapsack is reduced to your problem by multiplying its parameters by suitable $c$. This proves NP-hardness of your problem. $\endgroup$
    – Max Alekseyev
    Commented Apr 19, 2021 at 10:25
  • $\begingroup$ Hi Max, I have a follow up question. If I have one more constraint on $B$ which is $\sum_{h=1}^i (w_h+v_h)/2 =B$, is this problem still NP-hard? $\endgroup$
    – Rise of Kingdom
    Commented Apr 21, 2021 at 10:36
  • $\begingroup$ @EricHuang: Yes, it's also NP-hard. To reduce your original problem to this new one, we can consider two cases. If $\sum_h (w_h+v_h)/2 < B$, we add a new "useless" item with $v_* := 0$ and $w_* := 2B - \sum_h (w_h+v_h)$. If $\sum_h (w_h+v_h)/2 > B$, we add a new "super useful" item with $v_* := 1 + \sum_h v_h$ and increase $B$ by its capacity $w_* := v_* + \sum_h (w_h+v_h) - 2B > v_*$, implying that $(w_* + v_*)/2 + \sum_h (w_h+v_h)/2 = B + w_*$. $\endgroup$
    – Max Alekseyev
    Commented Apr 22, 2021 at 13:28
  • $\begingroup$ Hi Max, based on my understanding of your reduction. When $\sum_{h} (w_h+v_h)/2<B$, we will never choose the useless item, and the solution of the new problem is the solution of my original problem. When $\sum_{h} (w_h+v_h)/2>B$, we will always choose the ``super useful" item and the solution of the new problem is the solution of my original problem plus the "super useful" item. But how we can make sure that the "super useful" item will be always chosen in the new problem? Otherwise, the introduced extra weight $w_*$ will impact the solution of my original problem. $\endgroup$
    – Rise of Kingdom
    Commented Apr 22, 2021 at 14:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .