Taka notes are one of the systems where the greedy rule really does give the fewest notes.
What to build
A program that shows how to pay an amount with the fewest notes.
Requirements
- Use the notes 1000, 500, 100, 50, 20, 10, 5, 2 and 1.
- Take as many of the largest note as fit, then move to the next.
- Print only the notes that are used, and then the total number of notes.
Input
One number, the amount.
Output
One line per note used, largest first, with the note value and how many. The last line is total and the number of notes.
Constraints
1 ≤ amount ≤ 1000000.
Example
Input:
1789
Output:
1000 1
500 1
100 2
50 1
20 1
10 1
5 1
2 2
total 10
Why it works
In this set of notes, using several small notes where one larger note fits is never better, so taking the largest that fits is always right. That is a property of these values, and other coin systems do not have it.
Examples
Example 1 · Input
1789
Expected output
1000 1 500 1 100 2 50 1 20 1 10 1 5 1 2 2 total 10
Example 2 · Input
7
Expected output
5 1 2 1 total 2
Hints
Hint 1
Keep the note values in an array from largest to smallest.
Hint 2
For each note, `amount / note` says how many to use, and `amount % note` is what is left to pay.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int amount;
scanf("%d", &amount);
int notes[] = {1000, 500, 100, 50, 20, 10, 5, 2, 1};
int total = 0;
for (int i = 0; i < 9; i++) {
int used = amount / notes[i];
if (used > 0) printf("%d %d\n", notes[i], used);
amount %= notes[i];
total += used;
}
printf("total %d\n", total);
return 0;
}