Greedy Algorithm
I. In-Class Exercises
Programming Exercises
II. Knowledge Summary
Greedy Algorithm: Core Concept
The core idea of the Greedy Algorithm is: always pick the best option available! At each decision step, choose the option that looks optimal at the moment. Through a series of locally optimal choices, the algorithm ultimately achieves a globally optimal solution.
When to Use the Greedy Algorithm
The Greedy Algorithm is suitable for problems where locally optimal choices lead to a globally optimal solution. Such problems typically have these characteristics:
- Problems that seek a "best" value or optimal state
- Problems that require multiple steps of operations
- Each step's choice does not affect the optimal choice of subsequent steps (i.e., the problem has the greedy choice property)
Note that not all optimization problems can be solved with a Greedy Algorithm. If local optima do not lead to a global optimum, other methods such as dynamic programming should be used instead.
How the Greedy Algorithm Works
General steps for solving problems with the Greedy Algorithm:
- Identify the problem type: Determine whether the problem has the greedy choice property
- Formulate the greedy strategy: Determine the greedy rule for each step -- how to choose the optimal option at each step
- Verify correctness with counterexamples: Try to find counterexamples to verify whether the greedy strategy actually produces a globally optimal solution
Greedy Algorithm Examples
The following sorting algorithms all employ the Greedy Algorithm concept:
- Selection Sort: Each time, select the smallest (or largest) element from the unsorted portion and place it at the end of the sorted portion
- Bubble Sort: Each time, compare adjacent elements and move the larger (or smaller) element backward; each round "bubbles" the maximum to the end
- Insertion Sort: Each time, insert the first element of the unsorted portion into the correct position within the sorted portion
The common thread among these sorting algorithms is: each step makes the current optimal choice (select the smallest, swap the incorrect pair, insert at the right position), ultimately achieving an overall sorted result.
Execution Example of the Greedy Algorithm
Classic Greedy Problem: Making Change
Problem: Use the fewest coins to make 41 cents, with coin denominations of 25, 10, 5, and 1.
Greedy strategy: Always use the largest denomination coin possible.
| Step | Remaining Amount | Greedy Choice | Coin Used | Reason |
|---|---|---|---|---|
| 1 | 41 | Can we use 25? Yes | 25 x 1 | 41 >= 25, prioritize the largest denomination |
| 2 | 16 | Can we use 25? No | - | 16 < 25 |
| 3 | 16 | Can we use 10? Yes | 10 x 1 | 16 >= 10 |
| 4 | 6 | Can we use 10? No | - | 6 < 10 |
| 5 | 6 | Can we use 5? Yes | 5 x 1 | 6 >= 5 |
| 6 | 1 | Can we use 5? No | - | 1 < 5 |
| 7 | 1 | Can we use 1? Yes | 1 x 1 | 1 >= 1 |
| 8 | 0 | Done | - | Remaining is 0 |
Result: 4 coins used (25+10+5+1), which is indeed the optimal solution.
A Case Where Greedy Fails
Problem: Coin denominations are 1, 3, and 4. Make 6.
- Greedy strategy: 4 + 1 + 1 = 3 coins
- Optimal solution: 3 + 3 = 2 coins
This shows that the Greedy Algorithm is not always correct! When coin denominations do not satisfy certain conditions, the Greedy Algorithm may fail to produce the optimal solution, and dynamic programming is needed instead.
Problem-Solving Steps with the Greedy Algorithm
Example: Water Queue Problem
There are n people queuing to fill water. The i-th person takes t_i minutes. How should the queue be arranged to minimize the total waiting time for everyone?
Solution steps:
- Identify the problem type: Seeking "minimum total waiting time" -- an optimization problem with multiple steps, consider Greedy
- Formulate the greedy strategy: Let the person with the shortest filling time go first. Intuitively, letting faster people finish first reduces the waiting time for everyone behind them
- Verify the strategy: Suppose there are two people A (3 minutes) and B (5 minutes)
- A first, then B: A waits 0 min + B waits 3 min = total wait 3 min
- B first, then A: B waits 0 min + A waits 5 min = total wait 5 min
- Letting the faster person go first is indeed better
- Implementation: Sort the filling times, then calculate the total waiting time
1// Sort filling times in ascending order
2sort(t, t + n);
3int total_wait = 0;
4int current_wait = 0;
5for (int i = 0; i < n; ++i) {
6 total_wait += current_wait; // Waiting time for the i-th person
7 current_wait += t[i]; // Update cumulative time
8}
9cout << total_wait << endl;Common Mistakes with the Greedy Algorithm
- Not verifying the greedy strategy: Jumping straight to coding with a strategy that "seems reasonable" without verifying it through examples or counterexamples. Many greedy strategies seem intuitive but are actually wrong
- Greedy strategy is too vague: Descriptions like "pick the best each time" are too general -- you need to specify exactly what "best" means (largest? smallest? best ratio?)
- Applying Greedy to unsuitable problems: A classic example is the 0/1 knapsack problem -- greedy by value-to-weight ratio does not yield the optimal solution; dynamic programming is needed
- Wrong sorting direction: For example, the water queue problem should sort times in ascending order, but sorting in descending order by mistake
- Ignoring edge cases: For example, with only 1 person there is no waiting, or when all people have the same filling time, any order works equally well