Determine the combinations of making change for a given amount

Question

My assignment is to write an algorithm using brute force to determine the number of distinct ways, an related combinations of change for given amount. The change will be produced using the following coins: penny (1 cent), nickel (5 cents), dime (10 cents), and quarter (25 cents).

e.g.

Input: 16 (it means a change of 16 cents)

Output: can be produced in 6 different ways and they are:

1. 16 pennies.
2. 11 pennies, 1 nickel
3. 6 pennies, 1 dime
4. 6 pennies, 2 nickels
5. 1 penny, 3 nickels
6. 1 penny, 1 nickel, 1 dime

My algorithm must produce all possible change combinations for a specified amount of change.

---

I am at a complete loss as to how to even begin starting an algorithm like this. Any input or insight to get me going would be awesome.

Answer 1

Ok. Let me explain one idea for a brute force algorithm. I will use recursion here.

Let's you need a change of c cents. Then consider c as

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER

or simply,

c = ( p * 1 ) + ( n * 5 ) + ( d * 10 ) + ( q * 25 )

Now you need to go through all the possible values for p, n, d and q that equals the value of c. Using recursion, for each p in [0, maximumPennies] go through each n in [0, maximumNickels]. For each n go through each d in [0, maximumDimes]. For each d go through each q in [0, maximumQuarters].

p in [0, maximumPennies] AND c >= p
  |
  +- n in [0, maximumNickels] AND c >= p + 5n
       |
       +- d in [0, maximumDimes] AND c >= p + 5n + 10d
            |
            +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q

For any equality in these steps you got a solution.

Answer 2

You could start thinking about this problem by dividing it into sub-problems solve these and then change the problem and adjust your solution.

In your case you could first try to solve the problem using only pennies (With only one obvious solution of course), then look at nickels and pennies and look at all combinations there and so on. To improve this you can reuse solutions from earlier stages in your algorithm.

Answer 3

Well, if you want brute force solution, you can start with a very naive recursive approach. But to be efficient, you'll need a dynamic programming approach.

For the recursive approach:

1. find out the number of ways you can make using penny only.
2. do the same using penny and nickel only. (this includes step 1 also)
3. the same using penny, nickel and dime only (including step 2).
4. using all the coins (with all previous steps).

Step 1 is straightforward, only one way to do that.

For step 2, the recursion should be like this:

number of ways to make n cent using penny and nickel = 
    number of ways to make (n - [1 nickel]) using penny and nickel
    + number of ways to make n cent using penny only

Step 3:

number of ways to make n cent using penny, nickel and dime = 
    number of ways to make (n - [1 dime]) using penny, nickel and dime
    + number of ways to make n cent using penny and nickel only

Step 4 is similar.

And one thing to remember: you can make 0 cent in one way (i.e. using zero coins), it's the base case.