Minimum Coin Change Problem

Change-Making Problem¶

Greedy vs Dynamic Programming

In [1]:

# Greedy approach is fast, but fails for some denominations

import time
t=time.time()

def greedy(Denoms,Amt):
    coins = 0
    for i in Denoms:
        if i <= Amt:
            Q,R = divmod(Amt,i)
            print(Q,i)
            Amt = R
            coins += Q
    
    if R==0:
        return coins
    else:
        return -1

amount=63
denominations = [5,10,25,1,6]
denominations.sort(reverse=True)
print(denominations, amount)
    
print("Min Coins Required:", greedy(denominations,amount))

print("elapsed time: ",time.time()-t)

[25, 10, 6, 5, 1] 63
2 25
1 10
3 1
Min Coins Required: 6
elapsed time:  0.0012335777282714844

The true minimum is 5 coins...

In [2]:

# Recursive approach gives the correct answer, but is super slow

import time
t=time.time()

def minCoins(Denoms,Amt):
    Mcoins = Amt    # assumes coin with value "1"
    if Amt in Denoms:
        return 1
    else:
        for i in Denoms:    # for i in [x for x in Denoms if x <= Amt]: 
            if i <= Amt:
                Ncoins = 1 + minCoins(Denoms,Amt-i)
                if Ncoins < Mcoins:
                    Mcoins = Ncoins
    return Mcoins



amount=63
denominations = [5,10,25,1,6]
denominations.sort(reverse=True)
print(denominations, amount)
    
print(minCoins(denominations,amount))

print("elapsed time: ",time.time()-t)

[25, 10, 6, 5, 1] 63
5
elapsed time:  625.3406848907471

In [3]:

# Recursive approach with memoization

import time
t=time.time()

__memo = {}

def minCoins(Denoms,Amt):
    
    if Amt in __memo:
        return __memo[Amt]
    
    Mcoins = Amt    # assumes coin with value "1"
    if Amt in Denoms:
        __memo[Amt]=1
        return 1
    else:
        for i in Denoms:    # for i in [x for x in Denoms if x <= Amt]: 
            if i <= Amt:
                Ncoins = 1 + minCoins(Denoms,Amt-i)
                if Ncoins < Mcoins:
                    Mcoins = Ncoins
    
    __memo[Amt]=Mcoins
    return Mcoins

amount=63
denominations = [5,10,25,1,6]
denominations.sort(reverse=True)
print(denominations, amount)
    
print(minCoins(denominations,amount))
print(__memo)

print("elapsed time: ",time.time()-t)

[25, 10, 6, 5, 1] 63
5
{1: 1, 2: 2, 3: 3, 6: 1, 7: 2, 8: 3, 5: 1, 10: 1, 11: 2, 12: 2, 13: 3, 4: 4, 9: 4, 14: 4, 15: 2, 16: 2, 17: 3, 18: 3, 19: 4, 20: 2, 21: 3, 22: 3, 23: 4, 25: 1, 26: 2, 27: 3, 28: 4, 24: 4, 29: 5, 30: 2, 31: 2, 32: 3, 33: 4, 34: 5, 35: 2, 36: 3, 37: 3, 38: 4, 39: 5, 40: 3, 41: 3, 42: 4, 43: 4, 44: 5, 45: 3, 46: 4, 47: 4, 48: 5, 49: 5, 50: 2, 51: 3, 52: 4, 53: 5, 54: 6, 55: 3, 56: 3, 57: 4, 58: 5, 59: 6, 60: 3, 61: 4, 62: 4, 63: 5}
elapsed time:  0.0008664131164550781