Introduction to 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 obvious and immediate (local) benefit.
Unlike Dynamic Programming, greedy algorithms make a choice at each step that looks best at the moment, without ever backtracking or reconsidering past choices.
When to use Greedy Algorithms?
A problem can be solved using a Greedy approach if it satisfies two key properties:
- Greedy Choice Property: A global optimal solution can be arrived at by making locally optimal (greedy) choices at each step.
- Optimal Substructure: An optimal solution to the entire problem contains optimal solutions to its sub-problems.
Classical Example: Fractional Knapsack
Given a list of items with their values and weights, fill a knapsack of capacity W to maximize the total value. In the Fractional Knapsack problem, we are allowed to take fractions of items (e.g., cut an item).
The Greedy Strategy
Choose items by sorting them based on their Value-to-Weight Ratio (value / weight). This local choice leads to a global optimal solution.
Illustration
- Total Weight Taken: 10 + 20 + 20 = 50
- Total Value Obtained: 60 + 100 + 80 = 240
Another Example: Activity Selection
You are given N activities with their start and finish times. You need to select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
The Greedy Strategy
Always pick the activity with the earliest finish time that starts after or at the same time the previous activity finished.
For example, consider the following activities sorted by finish time:
- Activity 0: Start = 10, Finish = 20
- Activity 1: Start = 12, Finish = 25
- Activity 2: Start = 20, Finish = 30
A person can perform at most 2 activities: Activity 0 (10 to 20) and Activity 2 (20 to 30).