Greedy approach
- Algorithms course
- Intermediate
- Lesson 61/80
- 4 min
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.
Practice 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)).
Starter code
def greedy_one(coins, amount):
# Count the largest coinSample 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))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does greedy pick at each step?
- The local best Correct answer
- A random one
- The global best
- The first found
Explanation: The local best.
2 Greedy choice
amount ____ coinamount -= coinExplanation: -= is right.
3 Greedy approach: match the terms
| Term | Meaning |
|---|---|
greedy |
Local best |
global |
Whole problem |
backtrack |
None |
coin |
Coin |