Dynamic Programming and US Currency

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.

Advertisements

11 thoughts on “Dynamic Programming and US Currency

  1. Thanks a lot for sharing this with all people you actually know what you are talking about!
    Bookmarked. Please additionally discuss with my site
    =). We can have a link alternate arrangement between us

  2. Hi there are using WordPress for your site platform?
    I’m new to the blog world but I’m trying to
    get started and set up my own. Do you need any html coding expertise to make your own
    blog? Any help would be greatly appreciated!

  3. What’s up to all, the contents existing at this web page are in fact awesome for people experience, well, keep up the nice work fellows.

  4. I know this if off topic but I’m looking into starting my own blog and was wondering what all is needed to get set up? I’m assuming having a blog like yours
    would cost a pretty penny? I’m not very web smart so I’m not 100% certain.
    Any tips or advice would be greatly appreciated. Thanks

  5. Howdy just wanted to give you a quick heads up and let
    you know a few of the images aren’t loading properly. I’m not
    sure why but I think its a linking issue. I’ve tried it in two different web browsers and both show the same outcome.

  6. Howdy! Do you know if they make any plugins to assist with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing
    very good gains. If you know of any please share. Kudos!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s