Greedy Coin Systems

Canonical coin systems allow largest-first; US coins work, arbitrary sets may not.

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

• Prove greedy safe or exhibit counterexample amounts.
• DP gives optimal for general coins.
• Log coin usage for reconstruction problems.