Cash Register Algorithm

Goal:

Given a price, cash tendered, and two dimensional array of change ordered by denomination (pennies, dimes, quarters, etc.), return an array of exact change. Exceptions: return "insufficient funds" if there isn't exact change; return "closed" if exact change is equivalent to the contents of the array; return a warning if the price is greater than the cash tendered.

Analysis

First, check the difference between the price and cash tendered. If the price is greater than cash tendered, return an error. If the price equals the cash tendered, no change is needed. From this point, we assume the price is less than the cash tendered.

It helps to consider a simpler case where the cash tendered and the change on hand is all pennies and dimes.  You could proceed like this: (1) see if all of the change can be given in pennies.  If it can't (2) see if the remainder can be made up with dimes.  We could get the following cases:

A. All your pennies and some (or all) dimes are equal to the change due.  Done.

B. All your pennies and all your dimes are not enough.  Insufficient funds.

C. All your pennies and all your dimes are more than enough.  This is the case that's a little tricky, because you can run into the following problem:

You owe 3 pennies and 1 dime, but you have 1 penny and 2 dimes.  Assuming the customer has no extra pennies, there's no way to make them up.  Insufficient funds.

Otherwise, there are a few choices on how to give change, so the problem is deciding which is most efficient. You can work from the bottom up: give all your pennies and then make up the remainder with dimes.  This might not work.  You might owe 8 pennies and 1 dime but have 17 pennies and 1 dime.  You should exhaust the number of dimes due first, then exhaust the number of pennies. (Give 8 pennies back so that you have 9 pennies left, then give the dime.)

Breaking

The idea of "breaking" is what makes this exercise a little confusing. But it's important to note that it really isn't possible for the cashier to "break" higher denominations into lower denominations, which makes the problem a little bit easier.  The cashier only has so many pennies, and if she has a dime, she can't change that dime into pennies to "make up the difference."

Top Down vs. Bottom Up

So which is the best method?  Do you work down from higher denominations or do you work up from lower denominations?  It seems better to work up for the following reasons: (a) the computer isn't going to know where to start. If you start by giving back hundreds and that puts the change due into the negative, you skip to the next lower denomination. But that seems inefficient when you know that starting with the lowest denomination will give you something to work with. (b) If at any point you don't have enough of a given denomination to give back to the customer, you don't have enough period (see last point). So it seems like it will be more efficient to work your way up, too.  

On the other hand, it isn't good to try to give back everything in pennies and then make up the rest in dimes (previous paragraph). So working down makes sure that you don't have to worry about bad penny-dime combinations.  In that case, it seems like you give back up to 9 pennies before going to dimes, up to 9 dimes before going to dollars (or, to anticipate a bit, up to 4 pennies and 2 dimes before going to quarters...)

Handling the Data

It would be easiest to calculate how much is due, then divide that into number of pennies, nickles, dimes, and so on due.

Generalizing: the US System

The point about "breaking" is slightly complicated, perhaps, by the way the US coin system is set up. This affects the remarks about working up vs. working down.  A quarter is equal to an additional 25 pennies or 5 nickles.  So consider this case:

You owe 26 cents back; you have 3 dimes and 1 penny.  If you just work your way up from pennies to dimes you'll conclude there's no way to make change.  But if you also have 1 quarter, you can give back 1 quarters and 1 penny -- leaving you with 3 dimes.

Two Problems

Maybe it's best to consider cents and dollars in change as two separate problems.  First, figure out how to give back change in terms of cents (in fact, that's a mini-algorithm right there: given a register filled with pennies, dimes, and quarters, return the correct change for a given amount and a given cost). Here, I guess you work down from quarters to dimes to pennies.  Once you've handled cents, then dollars is a much easier problem.

Quarters, Fives, Twenties

A quarter reduces the number of pennies and dimes needed.  Odd numbers of quarters reduce the number of pennies needed by 5 but not even numbers of quarters -- so that's a complication.  If you don't have enough pennies, see whether using a quarter will give you enough pennies.  If not -- then you don't have enough pennies.

Quarters can also make up for missing dollars.  So it seems like after you've taken care of the pennies, you should make up as many dollars with quarters as you can.

Fives and twenties behave a little bit like quarters.  Odd numbers of fives reduce the number of dollars needed (by five, obviously).  Once you've made up all the dollars you need, you can reduce the number of tens needed with fives.

Twenties reduce the number of tens or hundreds needed.

Altogether, quarters, fives, and twenties add complexity to the problem, since they can be used to make up for missing amounts of lower or higher denominations...

But I suppose to a certain extent the same can be said of pennies or what have you, if there are a lot of them.  You might have 89 pennies but no dimes and owe 53 cents.  You should do it all with pennies in that case.  What's needed is a principled way to check whether you can make up what you owe with higher denominations when you lack lower denominations...