Making change for a canonical coin system is one of the simplest greedy algorithms, and one with which everyone is familiar. The algorithm is simply:
- Start with a list of coin values to use (the system), and the target value
- Find the largest coin that we can use
- Use as many of it as we can, subtracting their value from the total
- Stop when the remaining total is 0
Here is what it looks like in C:
unsigned int make_change(unsigned int *system, unsigned int *solution, size_t n, unsigned int amount) { unsigned int coin; int remaining = amount; /* Start with the first (highest valued) coin */ coin = 0; /* Main loop */ while (remaining > 0 && coin < n) { /* Find out if we can use this coin */ if (remaining >= system[coin]) { /* Use as many of this coin as we can */ solution[coin] = remaining / system[coin]; remaining = remaining % system[coin]; } /* Move to next coin */ coin++; } if (remaining > 0) { /* This means the coin system is not sensible */ return 0; } return 1; }
An example program:
#include <stdio.h> #include <stdlib.h> void print_solution(const unsigned int *system, const unsigned int *coins, size_t n, FILE *fout) { unsigned int coin; /* Print the number of each coin type used */ for (coin = 0; coin < n; coin++) { if (coins[coin]) { fprintf(fout, "%d x %d\n", coins[coin], system[coin]); } } } int main(void) { unsigned int system[] = {200, 100, 50, 20, 10, 5, 2, 1}; const size_t n = sizeof(system) / sizeof(unsigned int); unsigned int *coins = calloc(n, sizeof(unsigned int)); const unsigned int amount = 1741; unsigned int result = make_change(system, coins, n, amount); if (result) { print_solution(system, coins, n, stdout); } else { printf("No solution!\n"); } free(coins); return 0; }
Output:
8 x 200 1 x 100 2 x 20 1 x 1