🎓 A1Learner
🔍
0 of 112 lessons completed

DSA What Greedy Means

A greedy algorithm is a method that takes the locally best step at each stage. A greedy choice is never taken back later.

Greedy takes the biggest coin first

Greedy making 6 with coins [1, 3, 4] grabs a 4 coin first. Two 1 coins must follow it.

amount = 6
coins = [4, 3, 1]
used = []
rest = amount
for c in coins:
    while rest >= c:
        used.append(c)
        rest -= c
print(used)
print(len(used))

The table finds a better answer

A small table stores the fewest coins for each amount. Amount 6 needs only two coins here.

coins = [1, 3, 4]
dp = [0] * 7
for a in range(1, 7):
    dp[a] = 1 + min(dp[a - c] for c in coins if c <= a)
print(dp)
print(dp[6])

Example

def greedy_count(coins, amount):
    count = 0
    rest = amount
    for c in sorted(coins, reverse=True):
        while rest >= c:
            rest -= c
            count += 1
    return count

def optimal_count(coins, amount):
    big = amount + 1
    dp = [big] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]

rigged = [1, 3, 4]
for amount in [6, 10, 11]:
    print(amount, "greedy", greedy_count(rigged, amount), "optimal", optimal_count(rigged, amount))
plain = [1, 5, 10, 25]
for amount in [30, 40]:
    print(amount, "greedy", greedy_count(plain, amount), "optimal", optimal_count(plain, amount))

Key points

  • Greedy: taking the best-looking step now and never revisiting it
  • A locally best step is the best choice visible at one stage
  • A rigged coin system is a coin set built so the greedy step misleads
  • Greedy is fast because each step makes one simple choice
  • Greedy needs a proof before its answer can be trusted
  • Dynamic programming checks the rival choices that greedy skips

In this example, two counters race on the rigged coin set [1, 3, 4]. Greedy uses three coins for 6 because it grabs a 4 first. The table uses two coins, 3 plus 3. Greedy also trails at amount 10. The plain coin set [1, 5, 10, 25] shows matching counts at 30 and 40. A match on tested amounts is still not a proof for every amount.

Note

The Beginner course showed fewest coins by table in Coin Change, First Taste.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

With coins [1, 3, 4], why does greedy fail at amount 6?