Bryce Boe

Update 2011/02/25 12:07
Updated the code such that it doesn’t rely on a coin of denomination one.

I assisted in hosting the UCSB Programming Competition again this year. Doing so rekindled my love for dynamic programming algorithms, thus why I prepared an example similar to this one for my class and why I wrote this post.

In my own words, dynamic programming is a technique to solve a problem in which previous solutions are used in the computation of later solutions. The generic coin change problem is, given coins of a specified denomination and a number N what are minimum number of coins needed to make change for N? If you don’t like my definitions see wikipedia for dynamic programming and coin problem.

You might be asking yourself, why is this even difficult; don’t I always just take the largest coin possible, as is done when making change with US coins? You’re right, that approach works with US coins and this approach is called a greedy approach. However, if the coins are of value 1, 3, and 4 then the greedy approach would say the best way to make change of 6 is with three coins: 4, 1 and 1. As you’ve probably figured out the correct, or optimal solution is with two coins: 3 and 3.

As I’m very fond of python I coded up a solution which should work in any circumstance so long as 1 is one of the coin denominations. The solution works as follows: Calculate the minimum number of coins to make 1, 2, 3, …, all the way up to the number we want to make change for. At any given point, i, the minimum number of coins to make i is dependent upon previous solutions.

I’m going to be kind of lazy and not actually explain the process as the code is pretty self explanatory, with one addition: The code doesn’t just calculate the minimum number of coins, but rather calculates what coins were used to make the minimum at each point. See the code below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#!/usr/bin/env python
import os, sys
 
def solve_coin_change(coins, value):
    """A dynamic solution to the coin change problem"""
 
    table = [None for x in range(value + 1)]
    table[0] = []
    for i in range(1, value + 1):
        for coin in coins:
            if coin > i: continue
            elif not table[i] or len(table[i - coin]) + 1 < len(table[i]):
                if table[i - coin] != None:
                    table[i] = table[i - coin][:]
                    table[i].append(coin)
 
    if table[-1] != None:
        print '%d coins: %s' % (len(table[-1]), table[-1])
    else:
        print 'No solution possible'
 
 
if __name__ == '__main__':
    def usage():
        sys.stderr.write('Usage: %s value\n' % os.path.basename(sys.argv[0]))
        sys.exit(1)
 
    # Modify this to alter the denominations of coins
    coins = [1, 3, 4]
 
    if len(sys.argv) != 2:
        usage()
    try:
        value = int(sys.argv[1])
    except ValueError:
        usage()
    solve_coin_change(coins, value)

Related Entries

• Moving Images in 3D Space with Pyglet
• Defcon 19 Quals Forensics 100 and Forensics 300 Solution
• The Python Multiprocessing Queue and Large Objects
• UCSB’s International Capture The Flag Competition 2010 Challenge 6: Fear The EAR
• Properly Handling the Keyboard Interrupt Exception (SIGINT) within a Python C Module

Tags: python