Greedy limits

Greedy is not always optimal.

Greedy limits

Greedy is not always optimal. Example: [1, 3, 4] for amount 6. Greedy gives [4, 1, 1] (3 coins); the optimum is [3, 3] (2 coins).

In such cases dynamic programming is better; greedy makes a wrong choice.

So verify the problem structure before applying greedy; otherwise a wrong result arises.

Counter-example

An input showing an algorithm is wrong is a counter-example. It is used to test greedy's limits.

The [1, 3, 4] and 6 example above is one; greedy gives 3 coins, optimum is 2.

Counter-examples decide algorithm choice; they reveal a wrong approach early.

Exercise Greedy's worst case

Write greedy_bad(coins, amount). Return the greedy coin count. Print 3 with print(greedy_bad([1, 3, 4], 6)).

Show example solution

def greedy_bad(coins, amount):
    # Greedy worst case
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount = amount % coin
    return count
print(greedy_bad([1, 3, 4], 6))

Test yourself

Greedy limits: match the terms

counter-example

Shows flaw
greedy

Local best
DP

Global best
optimum

Best
How many coins does greedy give for [1, 3, 4] and 6?
- 1
- 2
- 4
- 3
Show answer

3 — 3 (4 + 1 + 1).

Optimum solution

Fewest coins for 6: ____ result

Show answer

Fewest coins for 6: 3, 3 result

Next lesson: Summary - Greedy

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies