At the end of a school fair you have tokens to spend at the prize stall. Each kind of prize is described by a tuple (cost, joy, stock): one copy costs cost tokens, makes you joy happy, and the stall has only stock copies of it. You may take any number of copies of a kind, from 0 up to its stock, as long as the total cost stays within tokens.
Implement max_joy(tokens: int, prizes: list[tuple[int, int, int]]) -> int: the largest total joy you can get.
max_joy(12, [(4, 5, 2), (3, 4, 1), (6, 8, 1)]) # 14 two of the first (8 tokens) + the second (3 tokens)
# three of the first would give 15, but only 2 are in stock
max_joy(2, [(5, 100, 3)]) # 0 can't afford anything
Unspent tokens are fine, and taking nothing gives 0.
Constraints: 0 <= tokens <= 2000, 0 <= len(prizes) <= 30, 1 <= cost <= 2000, 0 <= joy <= 1000, 1 <= stock <= 5. Trying every combination of counts (up to 6^30) is hopeless.
Show hint
a kind with stock = 3 is just three separate copies of the same prize, each usable at most once, so this becomes the 0/1 knapsack: best[t] = most joy within t tokens, and for each copy loop t downwards from tokens to cost.