Greedy Algorithms
A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate and obvious benefit.
1. The Core Concept
At every step, a greedy algorithm makes the locally optimal choice in the hope that this choice will lead to a globally optimal solution.
- Motto: "Take what looks best right now."
Unlike Dynamic Programming, which solves subproblems and might reconsider previous choices, a Greedy algorithm never looks back. Once a decision is made, it is final.
2. Key Properties
For a greedy algorithm to work correctly for a specific problem, the problem must exhibit:
- Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.
- Optimal Substructure: An optimal solution to the problem contains an optimal solution to subproblems.
3. Example: The Coin Change Problem
Problem: You need to give change for a specific amount (e.g., 36 cents) using the fewest number of coins. Available Coins: Quarter (25), Dime (10), Nickel (5), Penny (1).
Greedy Approach:
- Pick the largest coin less than or equal to the remaining amount.
- Subtract its value.
- Repeat until amount is 0.
- Step 1: 36 >= 25. Take one Quarter. Remaining: 11.
- Step 2: 11 >= 10. Take one Dime. Remaining: 1.
- Step 3: 1 >= 1. Take one Penny. Remaining: 0.
- Result: 3 coins (25, 10, 1). This is optimal for US currency.
Counter-Example:
If coins were {1, 3, 4} and target was 6:
- Greedy: 4 + 1 + 1 (3 coins).
- Optimal: 3 + 3 (2 coins). In this case, Greedy fails and Dynamic Programming is needed.
def greedy_coin_change(coins, amount):
# Coins must be sorted descending
coins.sort(reverse=True)
result = []
for coin in coins:
while amount >= coin:
amount -= coin
result.append(coin)
return result4. Pros and Cons
- Pros: Simple to implement, very fast execution time.
- Cons: Often does not provide the globally optimal solution for complex problems.