How do you make change?
I’ve always been fascinated by the denominations of money, and specifically, which coin values different countries use. Here in the US, we use the set of values {1,5,10,25}, and I’ve often wondered whether this is the best set of values. The question is: How do you figure out what ‘best’ is?
Previously, I wrote a program that, given a set like {1,5,10,25}, counted the number of coins needed to make every possible value between 1 and 99 cents. I thought that number would be a pretty good indication of how good the set of values was. The best set for 4 coins was a tie between {1, 5, 18, 29} and {1, 5, 18, 25}.
As I discussed this solution with my friends (long ago) they all mentioned that this wasn’t a very realistic or good measure of how well a set of values performs in the real world. It was suggested that a better metric would be to model real-world transactions, and the number of coins needed.
So, I set off to write a new program. The algorithm would model a single buyer and a number of ‘purchases’ between 0 and 99 cents. Then, I could calculate the average number of coins in the virtual ‘coin pocket’. This average pocket size would be my measure for the ‘best’ set of coin values. The pocket would contain an infinite number of dollar bills, so it never runs out of money, and the bills aren’t counted as ‘coinage’.
But, an interesting question came into play: When making a purchase, the program needs to decide how much to pay for the item, given the contents of the pocket. I started off by implementing a fairly naive algorithm that ended up preferring to use large coins. After looking at the results, I found that the pocket was accumulating as many as 18 pennies before spending them. Although this might be how I personally work, it didn’t seem to be how most people would do it, and it didn’t seem like a good model for the program. So, I pose the question to you, the reader!
If you’ve got 4 pennies and a bunch of dollar bills, do you usually put down pennies to ’round up’ your change? For example, would you pay $1.03 for an item that cost $0.38?
Would you put down extra nickels and dimes to ’round up’ to dimes and quarters? How often? For example, would you pay $1.08 or for an item that cost $0.38 to get back $0.70? This case is particularly interesting because you give up 4 coins (3 pennies and a nickel) to get back 4 higher valued coins (2 quarters and 2 dimes). There’s no reduction in the coin count, but it ‘feels right’ to get higher valued coins back.
How about $1.13 to pay for $0.38? In this case, you would get back exactly $0.75. What if the $0.13 was made up of 13 pennies? Would you still do it?
How about paying $1.63 for $0.88 to get back exactly $0.75? What if the $1.63 were made up of an odd assortment of coins, like 5 quarters, 2 dimes, 2 nickels and 8 pennies? Would you still do it?
At some point (like in the previous example) we start to trade off our own time needed to add and compose our purchase amount for the convenience of just ending the transaction. I think we also consider the cashier’s time and patience, since they may not tolerate waiting as we ponder and compose the ‘perfect’ amount. Not to mention the other people in line behind us!
I think the solution here is going to be a rule-based system, with things like:
If you have enough pennies to round up to the nearest $0.05, then do it.
If you have enough dimes & nickels to round up to the nearest $0.25, then do it.
Don’t overpay for the item by more than $0.50.
Don’t give the cashier more than N coins. (whats N?)
I’ve started to code up some of this stuff in C++, but I’m kind of stymied by trying to come up with a good generalized solution to this problem, especially since the rules conflict and overlap. (And note that any solution has to work for arbitrary values of coins, like {1,4,12,24})
How would you go about tackling this problem?
Tags: c++, coinage, denominations
January 30th, 2008 at 10:03 pm
Personally I hate pennies (and think they should be phased out, with every item for sale rounding to the nearest nickel), and my personal rule base is to get rid of them whenever I have them, no matter what. I don’t really care about nickels or dimes, but I like to keep and receive coins. If I’m in a hurry I won’t bother to overpay to round up, but otherwise I always do.
I once paid a $2.00 bridge toll with 200 pennies.
January 31st, 2008 at 7:50 pm
I try to maximize coins paid - coins returned as change. Or, to end up with as less coins as possible. But I don’t think much about it.
Regarding coin values, remember we are a base-10 society. It is a lot easier to make operations in 10s than in 14s.
Many countries do not have quarters, but halves. Easier to add 50s than 25s.
The algorithm should include a “mental cost”.
February 1st, 2008 at 10:23 pm
You suggest that fishing around for coins makes you lose face with the people behind you in line, but consider also that you lose face with the cashier.
Having had that job, I never give coins unless I don’t have bills that cover the sale. It never takes longer for the cashier to take the coins out of the neatly organized drawer than for you to fish it out of your pocket or wallet or change purse or whatever. If you are paying in cash, there’s a good chance the cashier earns minimum wage - have mercy on them.
If a computer were giving change, perhaps it would figure out the minimum number of coins needed for the entire transaction - $.86 from a dollar is five coins, but $.86 from a $1.11 might only be three - maybe two from the purchaser and one from the cashier, assuming she doesn’t have to break a roll of quarters.
Otherwise, keep in mind you are calculating the ideal set of coins for the purchaser only.
In reverse, this is actually a real-world problem. It takes time to make change, so minimize that activity. How much could you save if you never had to give change? Given a set of coin values, how do you ideally price items valued 0 to 99 cents, given some % sales tax, varying by state (and in California, County) - balance the loss against how many additional customers you might serve in 8 hours if you weren’t making change at the cost of 5 seconds per transaction.
February 2nd, 2008 at 8:25 am
Yes, it’s sometimes embarrassing if you are trying to fish the little coins out to make a payment. Especially when you don’t know the exact total until the taxes have been added at the end. But sometimes, if I do have plenty of coins, I consider doing THEM a favor by helping them have 1 dollar bills and quarters. This especially true when going to the Farmer’s market, where you’d think your 20 dollar bill was contaminated, so reluctant are they to give you e.g. 13 dollars change for it. The sales folk even prefer to round down to not have to deal with small change.
March 12th, 2008 at 3:54 am
i need a help, writing a flowchart that can do changes from a purchases with the minimum coins required..
im lost
March 12th, 2008 at 3:58 am
i need a help, writing a flowchart that can do changes from a purchases with the minimum coins required..
im lost, i dont know nothing of programming