make_change.py

# This is a greedy algorithm.
# Proof of correctness left as an exercise for the reader.
# https://en.wikipedia.org/wiki/Greedy_algorithm

def make_change(N, D):
    # Make sure the largest coins are first
    D.sort()
    D.reverse()

    # Solution is a map from coin value to # of that coin
    soln = {}

    # As long as there is still a monetary amount to make change for
    while N > 0:
        # Choose the largest coin that is less than N
        coin = get_largest_coin(N, D)

        if coin is None:
            # the amount left is less than the smallest coin.
            # this case is impossible so long as there are pennies.
            return None

        # Remove that coin's value from the amount we have left
        N -= coin

        # Count that coin towards the solution
        soln[coin] = soln.get(coin, 0) + 1

    return soln

# The same algorithm as above, but with tail recursion.
def make_change_recursive(N, D):
    D.sort()
    D.reverse()

    def f(n, running_soln):
        if n <= 0:
            return running_soln

        coin = get_largest_coin(n, D)
        if coin is None: return None
        running_soln[coin] = running_soln.get(coin, 0) + 1
        return f(n-coin, running_soln)

    return f(N, {})

# Returns the largest d in D where d <= N.
def get_largest_coin(N, D):
    for denom in D:
        if denom <= N:
            return denom

# This function does not rely on the assumption that the sum of two coins of
# the same value are not allowed to leapfrog the next largest coin.
# It uses dynamic programming. The return value is the minimum total number
# of coins required to make change.
def make_change_hard(N, D):
    # table[n] tells us the number of coins needed to make change for n cents.
    # let infinity denote that the solution DNE for a given n.
    # (this will also have a useful property w/ min later).
    table = [float('inf')]*(N+1)

    # you can make change for n=0 using 0 coins
    table[0] = 0

    # compute the number of coins needed for n=1 through N
    for n in range(1, N+1):
        # check each coin d
        for d in D:
            # if we can take this coin's value from n,
            if d <= n:
                # then would we be able to make change with fewer coins
                # than we currently think is the fewest?
                table[n] = min(table[n], table[n-d]+1)

    print(table)
    return table[N]

def print_solution(N, soln):
    print("To make change for", N, "cents:")
    total = 0
    for coin, count in soln.items():
        print("Use", count, "of", coin, "cent coin(s)")
        total += count
    print(total, "coins used in total")

if __name__ == '__main__':
    coins = [6, 5, 1]
    n = 10
    soln = make_change(n, coins)
    print_solution(n, soln)

    soln = make_change_recursive(n, coins)
    print_solution(n, soln)

    print(make_change_hard(n, coins))