497. 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.

Constraints - `1 ≤ k ≤ 100` - `0 ≤ amount ≤ 10000` - `1 ≤ denomination ≤ 10000` - `1 ≤ stock ≤ 1000`