#!/usr/bin/env python
coins = [1, 5, 10, 25] # North America
#coins = [1, 2, 5, 10, 20, 50] # Europe
def best_payment(coins, goal, bail):
# Given the available mixture of coins,
# what is the minimum number of coins required to reach the goal?
# Bail is the point where we give up, because a better solution has previously been found.
# Recursive.
if bail < 1:
return 999 # Forget it, someone else has already found a better solution
if goal == 0:
return 0 # Exact match
if len(coins) == 1:
return goal # Assuming that the smallest coin is a penny.
this_coin = goal/coins[0] # Integer division
best_run = 999
while this_coin >= 0:
bp = this_coin + best_payment(coins[1:], goal - this_coin*coins[0], bail - this_coin)
if bp < best_run:
best_run = bp
if bp < bail - this_coin:
bail = bp
this_coin -= 1
# print coins, goal, "=", best_run
return best_run
def test_coinset(coins):
# Given the available coins, what is the average number of coins
# needed to complete every transaction from 1 to 99?
coins.sort()
print "Coins:", coins
if coins[0] != 1:
print "This program requires that the currency has a penny."
return 0
coins.reverse()
total = 0
for x in range(1, 100):
bp = best_payment(coins, x, 100)
total += bp
print x, "->", bp
print "Average:", total/99.0
return total/99.0
test_coinset(coins)