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
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.
source to share
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
source to share