500. Some Items Are Mandatory
Each item has a weight, a value, and a flag saying whether it is MANDATORY. Every
mandatory item must be taken. Optional items may be taken or not. Print the largest total
value with total weight at most C, or -1 if the mandatory items alone do not fit.
items (w=2 v=3 must) (w=3 v=4) (w=4 v=6), C = 7 -> 9
The mandatory item costs weight 2 and gives value 3, leaving capacity 5, from which the
best optional choice is the (w=4 v=6) item, for 3 + 6 = 9.
## Reduce, do not complicate
The temptation is to add a dimension, or a per-item flag in the recurrence. Neither is needed.
Mandatory items are not a CHOICE, so they do not belong in the table at all:
``` fixedWeight = total weight of the mandatory items fixedValue = total value of the mandatory items
if fixedWeight > C: answer is -1 otherwise: answer is fixedValue + (0/1 knapsack over the OPTIONAL items with capacity C - fixedWeight) ```
A constraint that removes a decision should shrink the instance rather than enlarge the state. That is the whole lesson here, and it is worth reaching for before reaching for an extra axis.
## Why the reduction is exact
Any valid selection contains every mandatory item and some set of optional items whose
weight fits in what remains. Conversely any optional set fitting in C - fixedWeight
extends to a valid selection. The two families correspond exactly, and the values differ
by the constant fixedValue, so maximising one maximises the other.
No approximation, no case analysis.
## The impossible case
fixedWeight > C is the only way to fail, and it must be checked BEFORE the table is
sized. Skip it and C - fixedWeight is negative, which allocates a table of negative
length: a crash in some languages and, in Python, an empty list that then makes the final
read fail or silently return the wrong thing.
Three tests cover it. (w=5 v=1 must) (w=1 v=9) with C = 4 answers -1, and the same
items with C = 6 answer 10. And three mandatory items of weight 1 with C = 2 answer
-1 while C = 3 answers 3.
## A boundary worth noting
(w=1 v=0 must) with C = 1 answers 0. The mandatory item must be taken and is worth
nothing, so the answer is 0 and NOT -1: it fits, so the instance is feasible.
Distinguishing "feasible with value 0" from "infeasible" is the only thing that makes the
-1 meaningful, and both print differently only if the check is on WEIGHT rather than on
value.
## Cost
Time O(n C). Space O(C).
Constraints - `1 ≤ n ≤ 1000` - `0 ≤ C ≤ 2000` - `1 ≤ weight ≤ 2000` - `0 ≤ value ≤ 1000000` - the flag is `0` or `1`
Input
The first line contains two integers n and C.
Each of the next n lines contains three integers: the weight, the value, and 1 if the item is mandatory or 0 if optional.
Output
Print the largest total value, or -1 if the mandatory items alone exceed the capacity.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.