Skip to main content
edited body
Source Link

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

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

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?

added 11 characters in body; edited tags
Source Link

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 $B= \sum_{h=1}^i (w_h+v_h)/2$$\sum_{h=1}^i w_i <B< \sum_{h=1}^i 2w_i$? Is it still Np-hard under this constraint?

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 $B= \sum_{h=1}^i (w_h+v_h)/2$? Is it still Np-hard under this constraint?

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

Post Undeleted by Rise of Kingdom
Post Deleted by Rise of Kingdom
Source Link

Knapsack problem with capacity constraint

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 $B= \sum_{h=1}^i (w_h+v_h)/2$? Is it still Np-hard under this constraint?