Writing a program to find the different number of ways I can make change

[opfball91]

Hi there. I was looking for some help, mainly with the thought process that is involved with writing a program that takes an int input and returns the number of ways change can be made from that input using dollars, quarters, dimes, nickels, and pennies. I would like to solve this using recursion. Right now the idea I have involves seeing how many dollars goes into the input, using the remainder I can then see how many quarters go in, remainder of that see how many dimes go in, and so on down the line. Then the next time through do it with one less dollar until I'm using 0 dollars, then with quarters until I'm using 0 quarters, etc. etc. As I'm writing this I suppose the issue I'm having is turning my thoughts into code, but I'm also confused as to how to keep track of and decrement the amounts using recursion. Any help is very much appreciated.

[ajputnam]

Not exactly sure what your asking. Are you wanting change in quarters, dimes, nickels and pennies given an input like 10.47?

I would convert the dollars to cents first. For example $10.47 => 10.47*100 = 1047 cents. Then from there you could.

int cents = 1047;
int quarters = int(cents/25);

cents -= 25*quarters; //get remaining balance
int dimes = int(cents/10);

cents -= 10*dimes;
int nickels = int(cents/5);


int pennies = cents-5*nickels

Does that help at all? This is not recursive but could be made recursive I suppose.

[opfball91]

I'll try to clarify. I'm trying to get the total number of ways change could be given, given an input in pennies. I.e. input of 107 ($1.07) could be given in change as:

1 dollar
0 quarters
0 dimes
1 nickel
2 pennies

Or

0 dollars
4 quarters
0 dimes
1 nickel
2 pennies

and so on down the line, simply keeping track of the vast number of ways change could be given for that amount.

I've been making attempts using nested for-loops but always seem to run into issues. Here's an example of what I'm working on.

#include <iostream>

using namespace std;

long long int makeChange(int n){
int counter = 0;
int pennies;
int nickels;
int dimes;
int quarters;
int dollars;
int remainder;
if (n < 5){
        return 1;
        }
        else{
        dollars = n/100;
        quarters = n/25;
        dimes = n/10;
        nickels = n/5;
        pennies = n;
        if (dollars>=1){
        for (int i = dollars; i>0; i--){
                int dollarsUsed = i*100;
                remainder = n-dollarsUsed;
                quarters = remainder / 25;
                counter++;
                for (int j = quarters; j>0; j--){
                        int quartersUsed = j*25;
                        remainder = remainder-quartersUsed;
                        dimes = remainder / 10;
                        counter++;
                        for (int k = dimes; k>0; k--){
                                int dimesUsed = k*10;
                                remainder = remainder-dimesUsed;
                                nickels = remainder / 5;
                                counter++;
                                for (int l = nickels; l>0; l--){
                                        int nickelsUsed = l*5;
                                        remainder = remainder-nickelsUsed;
                                        pennies = remainder / 1;
                                        counter++;
                                        for (int m = pennies; m>0; m--){
                                                counter++;
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
return counter;
}

int main(){
int input;
cout << "Input your value here: ";
cin >> input;
cout << makeChange(input) << endl;
}

[dhayden]

Sometimes it helps to start with the data that you need. You need the number of coins/bills that you're making change with. And their values and names:

constexpr unsigned NumCoinTypes = 5;
const unsigned coinValues[NumCoinTypes] = { 100, 25,10, 5, 1};
const char *coinNames[NumCoinTypes] = {"dollars", "quarters", "dimes",
                                       "nickels", "pennies"};

For a recursive solution, you need to keep track of the change in your partial solution, along with how much change you still need to give. Here is a partial solution. The hard part is described in the comments at the bottom. Can you figure out how to do that part?

// Print all the ways to make amt in change.  The change array
// contains coins already in hand. The job of this function is to
// make change for amt, using the coins whose index is idx or greater.
// returns the number of combinations
int makeChange(int amt,
               unsigned change[NumCoinTypes],
               unsigned idx)
{
    int result = 0;
    // For debugging, print the values in this call
    cout << "makechange(" << amt << ',' << idx << ")\n";

    // error checking
    if (amt < 0 || idx >= NumCoinTypes) {
        cout << "Error\n";
        result = -1;
    } else if (amt == 0) {
        // Yeah!  No more change to make. Print out what you have
        for (unsigned i = 0; i < NumCoinTypes; ++i) {
            cout << change[i] << ' ' << coinNames[i] << ' ';
        }
        cout << '\n';
        result = 1;
    } else if (idx == NumCoinTypes-1) {
        // You're down to pennies. Add all pennies to the change, then
        // Call yourself recursively to print it out
        change[idx] += amt;
        result = makeChange(0, change, idx);
        // Now remove the change you added to restore the previous value.
        change[idx] -= amt;
    } else {
        // You can add up to "maxNum" coins of the current value
        unsigned maxNum = amt / coinValues[idx];
        for (unsigned i = 0; i <= maxNum; ++i) {
            // Add "i" coins to the change
            // call yourself recursively, asking for the new amount of change, and
            // telling the recursive call to add the next type of coin.
            // Remove "i" coins from the change to restore it to the previous value
        }
    }
    return result;
}