2 backpacks with the same capacity - why can't we just find the max value twice

If you are given one set of elements with values ​​and weights: [(w1, v2), (w2, v2), ... (wn, vn)] and two backpacks Knap1 and Knap2 of equal capacity C, the goal is to determine , what optimal subsets of elements S1 and S2 can enter into Knap1 and Knap2, respectively, and maximize the values ​​and capacity of the backpacks.

The wrong way to solve this problem would be to first fill Knap1 with the DP programming algorithm using all the items as candidates, and then populate Knap2 using the remaining items from Knap1.

I don't understand why this algorithm is incorrect if the two backpacks have equal capacity. Can anyone explain or provide an example?


source to share

2 answers

Suppose the capacity of the backpacks is 10 and we have these objects (weight, value):

(8, 200) (1, 10) (1, 10) (2, 15) (9, 100)

A greedy algorithm considering only one knapsack will use objects with weights of 8, 1, and 1 to estimate a value of 220, but if you think both bags explicitly leave 1 and take 2, it's better.



A counterexample :
Set S elements: (w_i, v_i)

   s_1=(1,2) , s_2=(2,1) , s_3=(3,10) , s_4=(4,7) 


Backpacks capacity: c_1 = c_2 = 5

In your first round of DP, items s_1

and will be taken s_3

that will lead to value 12

. Now there is s_4

also s_2

left for the second backpack . This way your algorithm will choose s_4

which will lead to the value 7

. s_2

will be left.
Overall value:19

Optimal solutions would be s_1

and s_4

in one backpack and s_2

and s_3

another. Optimal overall value:20



All Articles