Comparing Greedy Solution from Class

We came up with a very interesting "greedy" solution in class where we try to take the highest coins away that we can first. This works perfectly well for the 1, 5, 10, and 25 cent coints we're used to using, but it doesn't work when we use some more exotic values. Let's compare a memoized version "make_change" to "make_change_greedy" that Kevin and Brendan came up with in class, using 1, 7, 10, and 25 cent coins:

import numpy as np
import matplotlib.pyplot as plt

def make_change(coins, value, mem=None):
    """
    Returns ideal number of coins (memoized version)
    
    Parameters
    ----------
    coins: list of int
        The coins I have available to me
    value: int
        The value I'm trying to make
    
    Return
    ------
    * Minimum # of coins
    """
    if not mem:
        mem = {}
    minCoins = value
    for c in coins:
        if value-c >= 0:
            if not value-c in mem:
                sol = 1 + make_change(coins, value-c, mem)
                mem[value-c] = sol
            sol = mem[value-c]
            if sol < minCoins:
                minCoins = sol
    return minCoins

def make_change_greedy(coins, values):
    if values == 0:
        return 0
    max_val = np.max(coins)
    coins.remove(max_val)
    return values//max_val + make_change_greedy(coins, values%max_val)

coins = [1, 7, 10, 25]
amts = np.arange(1, 100)
sols = [make_change(coins, amt) for amt in amts]
sols_greedy = [make_change_greedy(coins.copy(), amt) for amt in amts]
plt.plot(amts, sols)
plt.plot(amts, sols_greedy, linestyle='--')
plt.legend(["One at a time", "Greedy"])
plt.title(coins);

As an example of where there's a disparity, we can see that making 41 cents should only take 5 steps: 4x10c + 1x1c. However, a greedy solution will first take 25 away, leaving 16. Then it will take 10 away, leaving 6. And the best it can do after that is 6x1c. So a greedy solution ends up taking 8 steps instead of 5!

By contrast, if we switch to ordinary coins, the greedy solution works just the same. But this is a cautionary tale about greedy solutions in general; sometimes we take steps that look good in the near term, but they end up trapping us into taking non-optimal steps later

coins = [1, 5, 10, 25]
amts = np.arange(1, 100)
sols = [make_change(coins, amt) for amt in amts]
sols_greedy = [make_change_greedy(coins.copy(), amt) for amt in amts]
plt.plot(amts, sols)
plt.plot(amts, sols_greedy, linestyle='--')
plt.legend(["One at a time", "Greedy"])
plt.title(coins);