Introduction
Greedy algorithms are a class of algorithms that make a series of choices, each of which looks the best at the moment. The idea is to make the locally optimal choice at each step with the hope of finding a global optimum. Greedy algorithms are often used for optimization problems.
Key Concepts
Characteristics of Greedy Algorithms
- 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.
Common Applications
- Activity Selection Problem
- Huffman Coding
- Kruskal's and Prim's Algorithms for Minimum Spanning Tree
- Dijkstra's Shortest Path Algorithm
Steps to Design a Greedy Algorithm
- Determine the optimal substructure: Prove that a global optimum can be constructed from local optima.
- Develop a recursive solution: Formulate the problem recursively.
- Prove that the greedy choice is safe: Show that making the greedy choice at each step leads to an optimal solution.
- Develop a greedy algorithm: Implement the algorithm iteratively.
Example: Activity Selection Problem
Problem Statement
Given a set of activities with start and end times, select the maximum number of activities that don't overlap.
Greedy Choice
Always select the activity that finishes first.
Algorithm
def activity_selection(start_times, end_times):
n = len(start_times)
activities = sorted(zip(start_times, end_times), key=lambda x: x[1])
selected_activities = []
last_end_time = 0
for start, end in activities:
if start >= last_end_time:
selected_activities.append((start, end))
last_end_time = end
return selected_activities
# Example usage
start_times = [1, 3, 0, 5, 8, 5]
end_times = [2, 4, 6, 7, 9, 9]
print(activity_selection(start_times, end_times))Explanation
- Sort activities by their end times.
- Iterate through the sorted list and select activities that start after the last selected activity ends.
- Update the end time of the last selected activity.
Output
Practical Exercises
Exercise 1: Coin Change Problem
Given a set of coin denominations and an amount, find the minimum number of coins needed to make the amount.
Solution
def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
count += amount // coin
amount %= coin
return count if amount == 0 else -1
# Example usage
coins = [1, 2, 5, 10]
amount = 27
print(coin_change(coins, amount))Exercise 2: Fractional Knapsack Problem
Given weights and values of items, and a knapsack with a maximum weight capacity, find the maximum value that can be carried in the knapsack.
Solution
def fractional_knapsack(weights, values, capacity):
index = list(range(len(values)))
ratio = [v/w for v, w in zip(values, weights)]
index.sort(key=lambda i: ratio[i], reverse=True)
max_value = 0
for i in index:
if weights[i] <= capacity:
max_value += values[i]
capacity -= weights[i]
else:
max_value += values[i] * (capacity / weights[i])
break
return max_value
# Example usage
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(fractional_knapsack(weights, values, capacity))Common Mistakes and Tips
- Not sorting correctly: Ensure that the list is sorted based on the greedy choice criterion.
- Incorrect greedy choice: Verify that the greedy choice leads to an optimal solution.
- Handling edge cases: Consider edge cases such as empty inputs or inputs where no solution is possible.
Conclusion
Greedy algorithms are powerful tools for solving optimization problems efficiently. By making the best local choice at each step, they can often find the global optimum. Understanding the greedy choice property and optimal substructure is crucial for designing effective greedy algorithms. Practice with various problems to master this technique.