# Greedy algorithm for making change in C

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:

1. Start with a list of coin values to use (the system), and the target value
2. Find the largest coin that we can use
3. Use as many of it as we can, subtracting their value from the total
4. 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;

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