439. Most Strings Within Two Budgets
You are given binary strings and two budgets: at most m zeros and at most
n ones in TOTAL across everything you choose. Print the largest number of
strings you can choose. Each string may be chosen at most once.
strings 10 0001 111001 1 0 with m = 5 zeros and n = 3 ones -> 4
Two things make this harder than a single-budget knapsack.
The state needs both budgets, so the table is two-dimensional and each string sweeps the whole of it. The value being maximised is the COUNT of strings, not their size, so every item is worth exactly 1 and the interest is entirely in what fits.
The sweep direction is the trap, and it is the same trap as problem 422 with one more dimension:
for each string, with z zeros and o ones:
for i from m down to z:
for j from n down to o:
dp[i][j] = max( dp[i][j], dp[i - z][j - o] + 1 )
BOTH inner loops must run downward. Going upward on either one lets
dp[i - z][j - o] already contain the current string, so it gets chosen twice,
which answers the unbounded question instead.
That is exactly the opposite of problem 438, where reuse is wanted and the sweep runs forward. The two problems differ in one word of the statement and one direction in the code.
Constraints - `1 ≤ k ≤ 600` - `0 ≤ m, n ≤ 100` - `1 ≤ length of each string ≤ 100` - Each string is made of `0` and `1`.
Input
The first line contains three integers k, m and n.
Each of the next k lines contains one binary string.
Output
Print the largest number of strings that fit within m zeros and n ones in total.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.