You have coins of k different values, and as many of each as you like. Make the amount A with the fewest coins. Print the number of coins, or -1 if A cannot be made at all.
What to build
A dynamic program that makes an amount with the fewest coins.
Requirements
- Let
best[x]be the fewest coins that makex, withbest[0] = 0. - For each
x, try every coin that fits. - Print -1 if the amount cannot be made.
Input
The first line has k and A (1 ≤ k ≤ 10, 0 ≤ A ≤ 5000). The second line has the k coin values, each from 1 to 10000.
Output
The fewest coins, or -1.
Constraints
1 ≤ k ≤ 10, 0 ≤ A ≤ 5000, and every coin is from 1 to 10000.
Example
Input:
3 6
1 3 4
Output:
2
Why it works
The last coin used is some coin c, and the rest must be the best way of making x - c. Trying every coin covers every possibility.
Examples
3 6 1 3 4
2
2 3 2 4
-1
Hints
Hint 1
Greedy (largest coin first) is not always right: try coins 1, 3, 4 and amount 6.
Hint 2
best[0] = 0. For x from 1 to A, best[x] = 1 + the smallest best[x - c] over the coins c <= x.
Hint 3
Use a big number such as 1000000 for amounts that cannot be made, and print -1 for them at the end.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#define INF 1000000
int best[5001]; // best[x] = the fewest coins that make x
int main(void) {
int k, A;
int coins[10];
scanf("%d %d", &k, &A);
for (int i = 0; i < k; i++) scanf("%d", &coins[i]);
best[0] = 0;
for (int x = 1; x <= A; x++) {
best[x] = INF;
for (int c = 0; c < k; c++)
if (coins[c] <= x && best[x - coins[c]] + 1 < best[x])
best[x] = best[x - coins[c]] + 1;
}
printf("%d\n", best[A] >= INF ? -1 : best[A]);
return 0;
}