# Minimum Coins Change Problem

Posted on May 21, 2012
by Ryan O'Neill

A question came up recently on how to write an algorithm where given a list of denominations of coins, what is a way to return the exact amount of change using the smallest number of coins possible.

Here is my solution which has not been fully optimized.

```
#!/usr/bin/python
import sys
def minimum_coins_change(denominations, value):
# Find the minimum number of coins necessary to
# provide the exact change. If exact change is
# not possible, return None
result = None
if value == 0:
# if the value left to compute is 0, we're done
# and so the value of all other denominations left
# is zero (if there are any)
result = { }
for denom in denominations:
result[denom] = 0
elif len(denominations) == 0:
# if the value is not zero and we have no denominations
# left to use, then we cannot make change using this
# set of denomination counts chosen
result = None
else:
# both the value and the number of denominations left
# to use are non zero
denom = denominations[0]
rest = denominations[1:]
rest_result = { }
max_count = value / denom
min_coin_count = sys.maxint
# loop through this denomination and test the different
# combinations available for the range of values
# for this denomination
for i in range(max_count + 1):
current_value = value - (denom * i)
rest_result = minimum_coins_change(rest, current_value)
# if we can make change given the remainder
if rest_result != None:
new_count = i + sum(rest_result.values())
# test to see if this new set is the minimum coin count
if new_count < min_coin_count:
# if so, set it to our result
min_coin_count = new_count
result = rest_result
result[denom] = i
return result
def print_result(denominations, value, result):
print "Smallest change for", value, "using denominations:", denominations
if result == None:
print " No change possible"
else:
print " %d coins needed" % sum(result.values())
print " distributed via", sorted(result.items())
print
denominations = [1]
value = 67
result = minimum_coins_change(denominations, value)
print_result(denominations, value, result)
denominations = [5]
value = 69
result = minimum_coins_change(denominations, value)
print_result(denominations, value, result)
denominations = [5, 1]
value = 43
result = minimum_coins_change(denominations, value)
print_result(denominations, value, result)
denominations = [100, 50, 25, 10, 5, 1]
value = 72
result = minimum_coins_change(denominations, value)
print_result(denominations, value, result)
denominations = [67, 42, 34, 15, 8]
value = 124
result = minimum_coins_change(denominations, value)
print_result(denominations, value, result)
```

Here is a running of the program.

```
rhino:python_code roneill$ python minimum_coins_change.py
Smallest change for 67 using denominations: [1]
67 coins needed
distributed via [(1, 67)]
Smallest change for 69 using denominations: [5]
No change possible
Smallest change for 43 using denominations: [5, 1]
11 coins needed
distributed via [(1, 3), (5, 8)]
Smallest change for 72 using denominations: [100, 50, 25, 10, 5, 1]
5 coins needed
distributed via [(1, 2), (5, 0), (10, 2), (25, 0), (50, 1), (100, 0)]
Smallest change for 124 using denominations: [67, 42, 34, 15, 8]
3 coins needed
distributed via [(8, 0), (15, 1), (34, 0), (42, 1), (67, 1)]
```