Greedy coin selection

Canonical — largest first; arbitrary fail.

Try this in Python

def greedy_coins(amount, coins):
    coins = sorted(coins, reverse=True)
    ans = []
    for c in coins:
        while amount >= c:
            ans.append(c)
            amount -= c
    return ans if amount == 0 else None

print(greedy_coins(63, [25, 10, 5, 1]))

Key takeaways

• Proof or counterexample.
• DP general.
• Reconstruct log.