Greedy approach

Pick the local best at each step.

Greedy approach

Greedy algorithms pick the local best at each step and never backtrack. They are simple and fast.

They may not always give the global best; choosing the right problem matters.

Greedy underlies Huffman coding, Kruskal and Dijkstra; it runs efficiently.

Local vs global

A greedy choice cannot be undone. So greedy works when local choices build the global optimum.

Otherwise a different strategy (DP, branch-and-bound) is needed; greedy falls short.

So before applying greedy, verify the problem has the greedy-choice property.

Exercise Pick largest coin

Write greedy_one(coins, amount). Take the largest coin as many times as possible in one greedy step. Return how many of the largest coin is used. Print 2 with print(greedy_one([25, 10, 5, 1], 63)).

Show example solution

def greedy_one(coins, amount):
    # Count the largest coin
    coins.sort(reverse=True)
    largest = coins[0]
    return amount // largest
print(greedy_one([25, 10, 5, 1], 63))

Test yourself

What does greedy pick at each step?
- The local best
- A random one
- The global best
- The first found
Show answer

The local best — The local best.
Greedy choice
```
amount ____ coin
```
Show answer
```
amount -= coin
```
Greedy approach: match the terms

greedy

Local best
global

Whole problem
backtrack

None
coin

Coin

Next lesson: Coin change

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies