Coin Change Algorithm C

Question

I'm having some trouble coming up with a working algorithm for the following problem.

Given determined quantities of available coins from 100, 50, 25 and 10 cents, I need to find how to fit a combination of these coins into a given value x. (it doesn't have to be optimal, any combination from availables coins will do).

So far, I've got this code, which works only for some cases.

struct coins{
    int valor;
    int quant;
};

int change = 0;
int changecoins[4] = {0};
struct coins available_coins[4] = { 0 };

moedas_disp[3].value = 10; //10 cents coins
moedas_disp[2].value = 25; //25 cents coins
moedas_disp[1].value = 50;  //50 cents coins
moedas_disp[0].value = 100; //100 cents coins

//quantity values just for test purposes
moedas_disp[3].quant = 10; //10 cents coins
moedas_disp[2].quant = 15; //25 cents coins
moedas_disp[1].quant = 8;  //50 cents coins
moedas_disp[0].quant = 12; //100 cents coins


for(int i=0; i<4; i++){
    while((change/available_coins[i].value>0)&&(available_coins[i].quant>0)){
        change -= available_coins[i].value;
        available_coins[i].quant--;
        changecoins[i]++;
    }
}
if(change>0){
    printf("It was not possible to change the value");
}
else{
    printf("Change:\n");
    printf("\t%d 100 cent coin(s).\n", changecoins[0]);
    printf("\t%d 50 cent coin(s).\n", changecoins[1]);
    printf("\t%d 25 cent coin(s).\n", changecoins[2]);
    printf("\t%d 10 cent coin(s).\n", changecoins[3]);
}

However for quantities like 30 this won't work. The program will fit 1 coin of 25 cents, but then have 5 cents left, which will fail to compute. This also occurs with 40, 65, and so on.

Thanks in advance!

Answer 1

You could use a recursive algorithm along the following steps:

• Take 1 100c coin and try to break down the remaining amount into only 50, 25, 10s
• If that didn't work, take 2 100c coins and try to break down the remaining amount into only 50, 25, 10s
• Etc.

If you tried every possibility for the number of 100c coins (including 0!) then you will have covered all possible solutions.

I wrote some demo code. If this is homework then please don't copy-paste my code but maybe write your own code once you understand the ideas involved ...

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool coin_find(unsigned int total, unsigned int *denom)
{
    if ( total == 0 )
        return true;    // Success - reduced total remaining to 0

    if ( *denom == 0 )
        return false;   // Failure - tried all coins in the list with no solution yet

    // Try 0 of the largest coin, then 1, etc.
    for (unsigned int d = 0; ; ++d)
    {
        if ( d * *denom > total )
            return false;

        if ( coin_find(total - d * *denom, denom + 1) )
        {
            if ( d ) 
                printf("%ux%uc ", d, *denom);
            return true;
        }
    }
}

int main(int argc, char **argv)
{
    if ( argc < 2 )
        return EXIT_FAILURE;

    unsigned int denoms[] = { 100, 50, 25, 10, 0 };

    long t = strtol(argv[1], NULL, 10);
    if ( t < 0 || t >= LONG_MAX )
        return EXIT_FAILURE;

    if ( !coin_find(t, denoms) )
        printf("No solution found");

    printf("\n");
}

Exercises for the reader:

1. Loop backwards instead of forwards so that we find tidier solutions by default.
2. Output only the breakdown with the smallest number of coins.
3. Output all possible breakdowns.

Bonus exercise:

• Rewrite this to not actually use recursion at all; instead use an array that holds the solution so far, and backtrack when you reach the end. Exercise 3 will actually be easier this way.