Fewest Coins With Limited Stock
Coins have denominations and a limited number of each. Print the fewest coins that sum
to exactly amount, or -1 if it cannot be done.
coins 1 x2, 3 x1, 5 x2, amount = 11 -> 3 5 + 5 + 1
coins 2 x3, amount = 5 -> -1 every total is even
Problem #481 is this with unlimited stock and problem 484 is the bounded MAXIMISATION. This one is the bounded minimisation, and it is here because the binary splitting of 484 has to be checked rather than assumed to carry over.
## The splitting, and why it still works
Replace a denomination with stock x by 0/1 pieces representing 1, 2, 4, ... coins
plus the remainder. A piece standing for q coins has value q * d and COUNT q.
For 484 the claim was that any number of originals from 0 to x is reachable by some
subset of pieces. That is a statement about the count alone, so it holds here unchanged.
What has to be checked separately is that the objective carries over. Taking a subset of
pieces summing to q originals contributes value q * d and count exactly q, which is
what q real coins would contribute. So the reachable pairs of (total, count) are
identical to the original problem's, and minimising over the pieces minimises over the
originals.
Splitting preserves the reachable SET, not just the reachable totals, and that is why it transfers from a maximisation to a minimisation without a new argument.
## The recurrence
dp[0] = 0, everything else infinity
for each piece (value, count):
for t from amount down to value:
dp[t] = min(dp[t], dp[t - value] + count)
Downward, because each piece is used at most once.
## The two impossible cases, which look different
coins 2 x3, amount = 5 is impossible for a reason about the denominations: every
reachable total is even.
coins 5 x1, 1 x3, amount = 9 is impossible for a reason about the stock: the
denominations could make 9, but only with four 1s and there are three.
Both print -1, and a solution that checks divisibility by the greatest common divisor
catches the first and misses the second. The table catches both, which is the argument for
using it.
Those two inputs sit next to coins 5 x1, 1 x4, amount = 9 answering 5, which is the
same denominations with one more coin of stock.
## Boundaries
amount = 0 answers 0, the empty selection. Not -1.
coins 7 x2, amount = 14 answers 2, using the entire stock of a single denomination.
The count reaches amount, so no 64-bit concern, but INF must be chosen so that
INF + count does not wrap.