503. Splitting Between Two Bags
There are two bags with capacities C1 and C2. Each item has a weight and a value,
and may go into the first bag, the second bag, or neither. Neither bag may exceed its
capacity. Print the largest total value carried.
items (w=2 v=3) (w=3 v=4) (w=4 v=6), C1 = 4, C2 = 4 -> 10
Bag 1 takes the (w=4 v=6) item and bag 2 takes the (w=3 v=4) item, leaving the first
item behind.
## Why one axis is not enough
The tempting reduction is to treat it as one bag of capacity C1 + C2. That is wrong: it
would allow an item set weighing C1 + C2 in total but impossible to divide, and it
always reports at least the true answer.
(w=6 v=8) (w=5 v=7) (w=4 v=5) with C1 = 6, C2 = 5 answers 15, from the first two
items. The combined-capacity reading allows total weight 11 and would also take 15 here, so
it happens to agree. (w=5 v=9) with C1 = 4, C2 = 4 answers 0, and the combined reading
gives capacity 8 and answers 9 for an item that fits in neither bag. That is the separating
case, and it is a test.
## The table
dp[c1][c2] = the largest value with at most c1 used in bag 1 and at most c2 in bag 2
for each item (w, v):
for c1 from C1 down to 0:
for c2 from C2 down to 0:
if c1 >= w: dp[c1][c2] = max(dp[c1][c2], dp[c1-w][c2] + v)
if c2 >= w: dp[c1][c2] = max(dp[c1][c2], dp[c1][c2-w] + v)
Three choices per item and only two of them write anything, because "neither bag" is the entry already sitting there.
## Both loops descend
Each item is used at most once, so both reads must see the state from before this item.
Both source entries are strictly smaller in exactly one coordinate, and descending both loops means neither has been written yet in this pass. Ascend either one and the item can go into that bag more than once.
This is problem 494's rule again: with d capacity axes, all d inner loops descend.
The difference here is that the two axes are ALTERNATIVES rather than simultaneous costs,
which changes the transitions and not the directions.
## Boundaries
C1 = C2 = 0 answers 0, with nothing carried.
(w=5 v=9) with C1 = 4, C2 = 5 answers 9: the item fits in the second bag only, so
the two capacities must be tracked separately rather than as a pair of equals.
(w=3 v=5) three times with C1 = 3, C2 = 6 answers 15: one item in the first bag and
two in the second, which needs the bags to be filled unevenly.
## Cost
Time O(n C1 C2). Space O(C1 C2).
Constraints - `1 ≤ n ≤ 50` - `0 ≤ C1 ≤ 200` - `0 ≤ C2 ≤ 200` - `1 ≤ weight ≤ 200` - `1 ≤ value ≤ 1000000`
Input
The first line contains three integers n, C1 and C2.
Each of the next n lines contains two integers: the weight and the value of one item.
Output
Print the largest total value that can be carried in the two bags.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.