Tag Archives: Making Change

Making change using dynamic programming in C

A coin system is canonical if the greedy algorithm for making change is optimal for all values. All coin systems in the world are canonical for obvious reasons. If a coin system is not canonical, the change-making problem becomes NP-hard. We can use dynamic programming to solve the change-making problem for abitrary coin systems.

This is another table-filling algorithm. The table has a column for every value from 0 to the target value, and a column for every coin. Each cell will be filled with the minimum number of the coins from that row upwards that are needed to make that value. When the table has been filled, the minimum number of coins for the target value can be read from the bottom-right-hand cell.

Below is an implemention in C. As with other dynamic programming algorithms, I have used pointers within the table to link each cell to the cell from which its value was derived. These pointers can then be used to read back how many of each coin was used in producing the solution. The function make_change() takes an array of coin values, its length, a target value, and the address of a pointer to which to assign the solution array. The solution array has an entry for each coin and indicates how many of each coin were used in the solution.

#include <stdlib.h>

struct change_entry {
    unsigned int count;
    int coin;
    struct change_entry *prev;
};
typedef struct change_entry change_entry;
 
unsigned int make_change(const unsigned int *coins, size_t len, unsigned int value,
        unsigned int **solution)
{
    unsigned int i, j;
    change_entry **table;
    unsigned int result;

    /* Allocate the table */ 
    table = malloc((len + 1) * sizeof(change_entry *));
    for (i = 0; i <= len; i++) {
        table[i] = malloc((value + 1) * sizeof(change_entry));
    }

    /* Calculate the values and build chains */ 
    for (i = 0; i <= len; i++) {
        for (j = 0; j <= value; j++) {
            if (i == 0) {
                /* Initialising the first row */
                table[i][j].count = j;
                table[i][j].coin = -1;
                table[i][j].prev = NULL;
            }
            else if (j == 0) {
                /* Initialising the first column */
                table[i][j].count = 0;
                table[i][j].coin = -1;
                table[i][j].prev = NULL;
            }
            else if (coins[i - 1] == j) {
                /* Can use coin */
                table[i][j].count = 1;
                table[i][j].coin = i - 1;
                table[i][j].prev = NULL;
            }
            else if (coins[i - 1] > j) {
                /* Can't use coin */
                table[i][j].count = table[i - 1][j].count;
                table[i][j].coin = -1;
                table[i][j].prev = &table[i - 1][j];
            }
            else {
                /* Can use coin - choose best solution */
                if (table[i - 1][j].count < table[i][j - coins[i - 1]].count + 1) {
                    /* Don't use coin */
                    table[i][j].count = table[i - 1][j].count;
                    table[i][j].coin = -1;
                    table[i][j].prev = &table[i - 1][j];
                }
                else {
                    /* Use coin */
                    table[i][j].count = table[i][j - coins[i - 1]].count + 1;
                    table[i][j].coin = i - 1;
                    table[i][j].prev = &table[i][j - coins[i - 1]];
                }
            }
        }
    }
    result = table[len][value].count;
    /* Read back the solution */
    *solution = calloc(len, sizeof(unsigned int));
    if (*solution) {
        change_entry *head;
        for (head = &table[len][value];
                head != NULL;
                head = head->prev) {
            if (head->coin != -1) {
                (*solution)[head->coin]++;
            }
        }
    }
    else {
        result = 0;
    }
    
    for (i = 0; i <= len; i++) {
        free(table[i]);
    }
    free(table);

    return result;
}
 

Here is an example program:

int main(void)
{
    unsigned int coins[] = {1, 2, 5, 10, 20, 50, 100};
    const size_t len = sizeof(coins) / sizeof(coins[0]);
    const unsigned int value = 252;
    unsigned int *solution;
    unsigned int result = make_change(coins, len, value, &solution);
    unsigned int i;
    printf("Number of coins: %u\n", result);
    printf("Coins used:\n");
    for (i = 0; i < len; i++) {
        if (solution[i] > 0) {
            printf("%u x %u\n", solution[i], coins[i]);
        }
    }
    free(solution);
    return 0;
}

The output:

Number of coins: 4
Coins used:
1 x 2
1 x 50
2 x 100

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;

    /* 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