485. One Item Per Group
Items are arranged in g groups. At most ONE item may be taken from each group, and
the total weight must not exceed C. Print the largest total value.
group 1: (w=2 v=3) (w=3 v=5)
group 2: (w=1 v=2) (w=4 v=7)
C = 5 -> 7
The answer takes (w=3 v=5) from group 1 and (w=1 v=2) from group 2, for weight 4
and value 7. Taking the best single item from each group independently would want
(w=3 v=5) and (w=4 v=7), which weighs 7 and does not fit.
## Why the ordinary 0/1 loop is wrong
0/1 knapsack processes one item at a time, updating dp in place with a downward
loop. That is correct when the only restriction is "each item at most once".
Here two items from the SAME group conflict. Process them one after the other in the
same dp array and the second can read an entry the first has already improved, which
means taking both.
group of (w=1 v=5) (w=1 v=6) (w=1 v=7), C = 1 -> 7
The answer is 7, one item. In-place processing of all three reaches 18.
## The fix
Process a GROUP as one step. Read from the state before the group and write into a separate copy:
for each group:
next = copy of dp
for each item (w, v) in the group:
for t from C down to w:
next[t] = max(next[t], dp[t - w] + v)
dp = next
Every candidate inside the group reads dp, which predates the group, so no two items
of one group can be combined. Writing to next is what enforces the restriction, and
it is the only change from ordinary 0/1 knapsack.
The copy per group is what costs the extra memory, and there is no way to avoid it with a single array: the whole point is that the group's items must not see each other.
## The initialisation, which is the second trap
next starts as a COPY of dp, not as a fresh array of negative infinity.
The copy is what encodes "skip this group". Initialise to negative infinity instead and you have required EXACTLY one item from every group, which is a different problem and is often infeasible.
Two tests are built for that. (w=5 v=100) alone in one group with C = 4 cannot be
taken at all, so under the forced reading the whole instance has no answer; the correct
answer is 3, entirely from the other group. And three groups each holding one item of
weight 3 with C = 7 answers 8, meaning two items: the third group must be skipped.
## Boundaries
C = 0 answers 0, since no item has zero weight.
Reading the answer as the maximum over the whole table is safe and is what the reference
solution does. Reading dp[C] also works with this formulation, because copying dp
forward keeps the table non-decreasing in t, and it is worth checking that you can say
why before relying on it.
Constraints - `1 ≤ g ≤ 100` - `0 ≤ C ≤ 5000` - `1 ≤ m` - the total number of items is at most `1000` - `1 ≤ weight ≤ 5000` - `1 ≤ value ≤ 1000000`
Input
The first line contains two integers g and C.
Then for each group: a line containing the group size m, followed by m lines each containing a weight and a value.
Output
Print the largest total value taking at most one item from each group.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.