Have you ever worked at a retail store, or paid close attention to a cashier at a retail store? If so, you’ve probably seen the process of “making change”. The problem is, in the US, as follows:
Given some desired amount, X = $D.cc, and the following coin/bill denominations {$100, $50, $20, $10, $5, $1, $0.25, $0.10, $0.05, $0.01}, how can you make X with the least number of bills/coins.
Most people (from the US, anyway) who see this problem will think it is exceptionally easy. You simply keep giving the customer the highest denomination that’s less than the amount you still owe them. For example, if you need to make $6.21 you need two bills and three coins ($5, $1, 2 x $0.10, $0.01). There is no other combination that will yield less than 5 total bills and coins in the US system.
If you’re a programmer, you’ll recognize this ‘algorithm’, as the greedy solution. With a simple proof, you can see that for US denominations the greedy solution is always optimal. If you’ve only ever thought about this problem in the real, physical world, you might think that this problem has a greedy optimal algorithm in all currency systems. But this is not true. Consider the following example:
How do you make change for $8 using the following denominations {$5, $4, $1}?
A fast-moving cashier using the greedy method would give a $5 and three $1′s, but that’s not optimal. You can see that in this (strange) currency system it’s better to give two $4′s. This is a simple example, but you can see how in a poorly conceived currency system change-making could require a lot of thought. In fact, the only way to give the optimal solution to this problem for any amount in any system is to use Dynamic Programming. We have the following DP algorithm which solves this problem in all cases:
Given coins denominations d1…dn such that d1 < d2 < … < dn (with d1 = 1, for simplicity), make change for an amount C using the least coins possible.
Let M[j] = optimal number of coins for an amount j
M[j] = min over all i (such that di <= j) of (M[j - di] + 1)
M[0] = 0
The algorithm for solving this program builds up from M[1] to M[C] with each one taking O(n) time to solve. That leads to an O(n*C) time algorithm. The greedy algorithm was just O(C), so this DP algorithm is much harder when you have a complicated currency system with many denominations. If you’re a cashier forced to solve this quickly in your head hundreds of times a day, you don’t have time to run anything but the greedy method!
Before reading this, you might have thought, as I did, that the denominations we use every day were chosen because they are convenient round numbers. But now I hope that you can see how currency denominations are a carefully tuned system that yield a greedy solution to common problems. This is just one cool example of how humans are constantly optimizing algorithms, even when there’s not a computer or computer scientist in sight.
