494. The Bag With a Count Limit
Each item has a weight and a value and may be used at most once. The total weight must
not exceed C, and the NUMBER of items taken must not exceed K. Print the largest
total value.
items (w=2 v=3) (w=3 v=4) (w=4 v=6), C = 7, K = 2 -> 10
Two constraints apply at once, so the table needs two axes. Neither constraint implies
the other: dropping K makes this problem #236, and dropping C makes it "take the K
most valuable items", which is a sort.
items (w=2 v=2) (w=2 v=2) (w=2 v=2), C = 6, K = 2 -> 4
Here the capacity allows all three and the count does not, which is the clearest sign that both axes are needed.
## The table
dp[c][j] = the largest value using total weight exactly c with exactly j items,
or unreachable
dp[0][0] = 0, everything else -infinity
for each item (w, v):
for c from C down to w:
for j from K down to 1:
if dp[c-w][j-1] is reachable:
dp[c][j] = max(dp[c][j], dp[c-w][j-1] + v)
answer = max over all reachable dp[c][j]
## Both loops run downward
The reason is the same as in one dimension, applied twice. Each item may be used at most once, so both reads must see the state from before the item.
c decreasing handles the weight axis and j decreasing handles the count axis. Get
one of them wrong and the item can be used again with an extra count or an extra weight,
and the answer comes out too high. Both wrong and it can be used arbitrarily often.
The general rule is worth stating: in a 0/1 knapsack with d constraint axes, ALL d
loops run downward, and the item loop stays outermost.
## Exact versus at most
Defining the table on EXACT weight and EXACT count, then taking the maximum over everything reachable at the end, is easier to reason about than an at-most table, because the recurrence is then a plain shift with no monotonicity to maintain.
The cost is that the final answer needs a scan rather than a single read, and that the unreachable sentinel has to be guarded, exactly as in problem 491.
## Boundaries
K = 0 answers 0. No items may be taken, and the empty selection has value 0, so it is
0 rather than -1.
(w=1 v=1) (w=2 v=5) (w=3 v=9) with C = 6, K = 2 answers 14, from the second and
third items, using weight 5 of the 6 available. Neither constraint is tight, which is
the case a solution that always fills the bag gets wrong.
(w=5 v=9) (w=1 v=1) (w=1 v=1) with C = 6, K = 3 answers 10: the count permits all
three but the weight does not, so one small item is left behind.
## Cost
Time O(n C K). Space O(C K).
Constraints - `1 ≤ n ≤ 200` - `0 ≤ C ≤ 1000` - `0 ≤ K ≤ 200` - `1 ≤ weight ≤ 1000` - `1 ≤ value ≤ 1000000`
Input
The first line contains three integers n, C and K.
Each of the next n lines contains two integers: the weight and the value of one item.
Output
Print the largest total value using at most C total weight and at most K items.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.