University of Calgary

making change

Making Change
source: Katrin Becker

The "Greedy Algorithm" is one of a class of algorithms that deals with optimization. Typically, these algorithms go through a series of steps, with a set of choices to be made at each step. The goal (and what makes it an optimization problem) is to choose in such a way that the solution to the problem is in some sense the best (optimal). The Greedy Algorithm always makes the choice that looks the best at the moment (i.e. it doesn't look too far ahead to see if a different choice might work out better in the end.). It gets its name from always choosing the 'biggest'. This approach does not always lead to the best solution in all problems but there are many applications where it does (making change is one). Sometimes this approach merely leads to a solution that's "good enough" (sometimes the amount of work involved in finding a better solution is so much work itself that there's no point in trying).

One example of the Greedy Algorithm in real life is the way people used to make change (before all the cash registers started doing it for us). The optimal part of the problem is to find the minimal number of coins/ bills to return. The Greedy Algorithm leads to an optimal solution when making change precisely because of the coins and bills that we have. Using the Greedy Algorithm to make change for $1.00 for something costing $0.62 would result in:

we must give back $0.38, so...
1 quarter (always start with the biggest we can), leaving $0.13
next choose a dime, leaving $0.03
last we can only choose 3 pennies.

What makes it optimal is that there is no other combinations of coins totalling $0.38 that involve fewer than 5 coins.

[Question: what denomination coin/bill would make this approach fail to give optimal results?]

Your job for this assignment is to write a program that will read in an amount charged and an amount tendered and then calculate the number and size (denomination) of coins/ bills to return as change. Assume we have the following denominations available:

$50.00, $20.00, $10.00, $5.00 bills
$2.00, $1.00, $0.25, $0.10, $0.05, $0.01 coins

You should be able to read in any amount charged and tendered (less than $10,000.00) and have your program print a readable list of what change to return.

Your program should be friendly without being too verbose, and it should be reasonably robust (provided the user typed in valid numbers the program should NOT blow up).

The program must be fully documented and follow appropriate style constraints. You must provide sufficient evidence that the program compiles and executes correctly.


Notes on Marking:
oIn order to pass it must work. (Some marks will be given to all *reasonable* attempts, working or not)


o good, clean design;
o good documentation
o checks for amounts in range
o 0 - 10000
o checks for amount tendered < amount charged
o user interface reasonable?
o adequate testing?


Important Note: if your program does not function properly it is possible to verify that some parts work if you have produced a reasonable trace (see sample solution)


BONUS:

1. Make your program loop so users can enter more than one amount per run.

2. Allow the user to enter amounts in either U.S. or CDN dollars and do the conversions, giving the amount of change to return in each.



Updated: August 31, 2005 08:34 AM