I'm coding a brute-force algorithm on change making and I'm a little stuck

Question

I need to write a program that uses brute-force method to find out how to make change the most efficiently. I'm a little confused and I'm curious if I'm on the right track. I'm writing it in C.

It does not use a greedy algorithm.

It's just confusing me is all. In the end it should output the most efficient change as toonie, loonie, quarter, dimes, nickels, pennies, in that order. (Like 1 1 0 0 1 0.)

Am I on the right track? I'm a little confused as to what I'm doing, six for loops is apparently the key, and I'm adding each iteration, but as to what's going on conceptually I'm a little confused.

#include <stdio.h>

int main(int argc, char *argv[]) {
    //Input
    int amount = 336;
    int bestSolution = amount;
    //Coins
    int toonies = 0, loonies = 0, quarters = 0, dimes = 0, nickels = 0, pennies = 0;
    int amountAfterToonies, amountAfterLoonies, amountAfterQuarters, amountAfterDimes, amountAfterNickels;
    //Counters
    int i, j, k, l, m, n;

    for (i = 0; i < amount / 200; i++) { //Finds amount 
        toonies++;
        amountAfterToonies = amount % 200;
        for (j = 0; j < amountAfterToonies / 100; j++) {
            loonies++;
            amountAfterLoonies = amountAfterToonies % 100;
            for (k = 0; k < amountAfterLoonies / 25; k++) {
                quarters++;
                amountAfterQuarters = amountAfterLoonies % 25;
                for (l = 0; l < amountAfterQuarters / 10; l++) {
                    dimes++;
                    amountAfterDimes = amountAfterQuarters % 10;
                    for (m = 0; m < amountAfterDimes / 5; m++) {
                        nickels++;
                        amountAfterNickels = amountAfterDimes % 5;
                    for (n = 0; n < amountAfterNickels; n++) {
                        pennies++;
                        sum = toonies + loonies + quarters + dimes + nickels + pennies;
                        if (sum < bestSolution) {
                            bestSolution = sum;
                        }
                    }
                }
            }
        }
    }
}
printf("%d %d %d %d %d %d\n", toonies, loonies, quarters, dimes, nickels, pennies);
printf("%d\n", bestSolution);
return 0;
}

Answer 1

You don't find most efficiently way. You find all ways.

I suggest you something like:

toonies=amount/200;
amount%=200;
loonies=amount/100;
amount%=100;
//and so on

(Even if you want to keep the loops, separate them - there is no reason to use nested loops)

Answer 2

The algorithm depends on whether or not a "greedy" algorithm will work. Greedy works in the US and I think in Canada, but would not work, eg, if there were a 15-cent piece or a $3 bill.

For "greedy", you take the total amount of change received, repeatedly subtract the largest bill/coin until the amount is less than the bill/coin value, then bump down to the next smaller bill/coin.

Several ways to do it, but it could be done efficiently in two nested loops and an array containing the bill/coin values. Or you could have N sequential loops, one for each bill/coin value. In this case the loops would not be nested. Basically, each loop would be

while (amountDue >= bill_coin_values[i]) {
    bills_coins_to_dispense[i]++;
    amountDue -= bill_coin_values[i];
}

(Of course, the above loop can be replaced with modular division, but that kind of confuses the issue at this stage of development.)

But stick that loop in a loop that increments i through the list of values, and you have to two loop version.

Ie, the outer loop would be something like:

int numSizes = 7;
int bill_coin_values[] = {200, 100, 50, 25, 10, 5, 1};
int bills_coins_to_dispense[7];
for (int i = 0; i < numSizes; i++) {
    bills_coins_to_dispense[i] = 0;
    <Above loop>
}

Answer 3

Your solution will find all possible solutions.

What do you mean by the most efficient?

The step you need to add is to record whatever you consider to be the most efficient solution and present that as the answer at the end.

Edit - Correction; you're on the right track but if you track through the logic you first posted, you'll see you never get to adding pennies. This is because on the first iteration where you actually get a valid result, amountAfterDimes / 5 is 0 so you never add any pennies and therefore never find the correct answer.

You need to allow your search to try 0 of each coin to allow it to descend to the correct answer.

Answer 4

Maybe it's the Loonies and Toonies added to insomnia ... but this was too fun not to answer ...

#include <stdio.h>
struct coin {
   char *name;
   int     value;
   int     number;
};
#define NUMCOINS 7
int main(int argc, char *argv[]) {
   //Input
   int amount = 336;
   //Coins
   struct coin coins[NUMCOINS]={{"toonies", 200, 0},{"loonies",100,0},{ "four bit", 50,0},{ "two bit", 25,0},{"short bit",10,0},{ "nickels",5,0},{"pennies",1,0}};
   //Counters
   int i;

   for(i=0;i<NUMCOINS;i++)
     for (;amount >= coins[i].value; amount-=coins[i].value,coins[i].number++);

   for(i=0;i<NUMCOINS;i++)
     printf("%s %d \n",  coins[i].name, coins[i].number);


 return 0;
}