Find the fewest coins that add up to the amount, with an unlimited supply of each coin value. Greedy (always the biggest coin) does not always work.
Input
The first line has k and amount (1 ≤ k ≤ 12, 0 ≤ amount ≤ 10⁴). The second line has the k coin values (1 to 10⁴).
Output
The fewest coins, or -1 if the amount cannot be made.
Examples
Example 1 · Input
3 11 1 2 5
Expected output
3
Example 2 · Input
3 6 1 3 4
Expected output
2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
fewest[a] = the fewest coins that make amount a; fewest[0] = 0.
Hint 2
fewest[a] = 1 + min(fewest[a − c]) over the coins c ≤ a.
Hint 3
Amounts that cannot be made stay at infinity; print -1 for them.
Solution
Show one correct solution (try it yourself first)
k, amount = map(int, input().split())
coins = list(map(int, input().split()))
INF = float("inf")
fewest = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a and fewest[a - c] + 1 < fewest[a]:
fewest[a] = fewest[a - c] + 1
print(fewest[amount] if fewest[amount] != INF else -1)