# 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?

+4

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.

+5

source

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`

+8

source

All Articles