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

Because 25%10 is not equal to 0, You need to consider it. Try this algorithm:

#include <stdio.h>

struct coins{
    int value;
    int quant;
};

int main()
{
    int change = 30;
    int changecoins[4] = {0};
    struct coins available_coins[4] = { 0 };
    int temp;

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

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


    if(((change/10 < 2)&&(change%10 != 0)) || (change/10 >= 2)&&((change%10 != 5) && change%10 != 0)) {
        printf("It was not possible to change the value\n");
        return 0;
    }
    else {
        for(int i=0; i<2; i++){
            changecoins[i] = change / available_coins[i].value;
            change = change % available_coins[i].value;
            if(changecoins[i] >= available_coins[i].quant) {
                change = change + (changecoins[i] - available_coins[i].quant) * available_coins[i].value;
                changecoins[i] = available_coins[i].quant;
            }
        }

        if(change%10 == 5) {
            if(available_coins[2].quant < 1) {
                printf("It was not possible to change the value\n");
                return 0;
            }
            else {
                changecoins[2] = change / available_coins[2].value;
                change = change % available_coins[2].value;
                if(changecoins[2] >= available_coins[2].quant) {
                    change = change + (changecoins[2] - available_coins[2].quant) * available_coins[2].value;
                    changecoins[2] = available_coins[2].quant;
                }
                if(change%10 == 5) {
                    changecoins[2]--;
                    change = change + available_coins[2].value;
                }
            }
        }

        changecoins[3] = change / available_coins[3].value;
        change = change % available_coins[3].value;
        if(changecoins[3] >= available_coins[3].quant) {
            change = change + (changecoins[3] - available_coins[3].quant) * available_coins[3].value;
            changecoins[3] = available_coins[3].quant;
        }

        if(change>0) {
            printf("It was not possible to change the value\n");
        }
        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]);

            for(int i = 0; i < 4; i++) {
                available_coins[i].quant -= changecoins[i];
            }
        }
    }
    return 0;
}

Answer 2

The following solution uses Dynamic Programming and you can use it as long as the value of M (x for you) is small. If prev[j] is different than -1 then this means that j can be made with the given coins. coin[j] store the value of the coin used to make j, and prev[j] is the value without using coin[j]. Thus, (j - prev[j]) / coin[j] give us the number of coins of denomination coin[j] used to make weight j.

#include <stdio.h>

const int
    COINS = 4;

int M = 1100; 
int prev[10000];
int coin[10000];
// Available denominations.
int value[COINS] = { 10, 25, 50, 100 };
// Available quantities.
int quant[COINS] = { 10, 15, 8, 12 };
// Number of selected coins per denomination.
int answer[COINS] = { 0, 0, 0, 0 };

int main() {
    // base case    
    prev[0] = 0;
    for (int i = 1; i < 10000; i++)
        prev[i] = -1;

    // dynamic programming
    for (int i = 0; i < COINS; i++)
        for (int j = M; j >= 0; j--)
            if (prev[j] != -1) {
                int k = 1;
                while (k <= quant[i] && j + k * value[i] <= M) {
                    if (prev[j + k * value[i]] == -1) {
                        prev[j + k * value[i]] = j;
                        coin[j + k * value[i]] = value[i];
                    }
                    k++;
                }
            }

    // build the answer
    if (prev[M] != -1) {
        int current = M;
        while (current > 0) {
            int k = 0;
            while (k < COINS && coin[current] != value[k])
                k++;
            answer[k] += (current - prev[current]) / coin[current];
            current = prev[current];
        }
        printf("Change\n");
        for (int i = 0; i < COINS; i++)
            printf("\t%d %d cent coin(s).\n", answer[i], value[i]);
    } else {
        printf("It was not possible to change the value");
    }

    return 0;
}

Answer 3

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.