Imagine going to a store to buy something, and the shopkeeper gives you 1 yuan and 7 jiao as change. How would the shopkeeper give it? Usually, he would first give you one 1-yuan coin (if available), then a 5-jiao coin, followed by 1-jiao coins, using the fewest coins necessary to amount to the sum. This “always choose the best option in the current state, regardless of the future” approach is actually the core idea of the greedy algorithm.
What is the Greedy Algorithm?¶
The Greedy Algorithm is an algorithm that, at each step, makes the locally optimal choice (i.e., the best choice for the current state) and hopes that a sequence of such local optimal choices will lead to the globally optimal solution.
In simple terms, it’s like a “near-sighted” decision-maker: it only looks at immediate benefits without considering long-term consequences. The key to this strategy is whether the problem satisfies the “greedy choice property”—that is, the locally optimal choice at each step can ultimately lead to the globally optimal solution. If this property holds, the greedy algorithm can solve the problem efficiently; if not, it may yield a suboptimal solution.
Change-Making Problem: A Classic Application of the Greedy Algorithm¶
The change-making problem is the most classic example of the greedy algorithm. Suppose we have the following coin denominations: 25 cents (quarter), 10 cents (dime), 5 cents (nickel), and 1 cent (penny). We need to make 67 cents with the fewest coins possible.
Problem Analysis¶
Goal: Use the minimum number of coins to make 67 cents.
Core Idea: Start with the largest denomination and take as many as possible of the current denomination until the amount is zero. This strategy guarantees a local optimum, and thus a global optimum, provided the coin denominations satisfy the condition that “no larger denomination can be formed by the sum of smaller denominations” (e.g., 25, 10, 5, 1).
Step-by-Step Calculation (Example: 67 Cents)¶
- Sort denominations in descending order:
[25, 10, 5, 1]. -
Take the largest denomination first:
- 25 cents: 67 ÷ 25 = 2 (take 2 coins), totaling 50 cents. Remaining: 67 - 50 = 17 cents.
- 10 cents: 17 ÷ 10 = 1 (take 1 coin), totaling 10 cents. Remaining: 17 - 10 = 7 cents.
- 5 cents: 7 ÷ 5 = 1 (take 1 coin), totaling 5 cents. Remaining: 7 - 5 = 2 cents.
- 1 cent: 2 ÷ 1 = 2 (take 2 coins), totaling 2 cents. Remaining: 0 cents. -
Total coins: 2 (25¢) + 1 (10¢) + 1 (5¢) + 2 (1¢) = 6 coins.
Verify Optimality¶
Is there a better combination? For example, “50¢ + 10¢ + 5¢ + 2×1¢” also uses 6 coins, so no improvement is possible. This confirms the greedy algorithm yields the optimal solution here.
Limitations of the Greedy Algorithm¶
The greedy algorithm is not universal. If the problem does not satisfy the property that “local optimality leads to global optimality,” the algorithm will fail. For example:
- Denominations: [1, 3, 4] (no 2¢ coins), target amount 6¢.
- Greedy strategy: Take 4¢ first, then 2×1¢, totaling 3 coins.
- Optimal solution: Take 3¢×2, totaling 2 coins.
Here, the greedy algorithm fails because the local optimal choice (taking 4¢) leads to a worse global solution. Thus, the greedy algorithm only works for problems with the “greedy choice property”—i.e., each choice of the largest denomination leaves a subproblem with the same structure as the original problem.
Applicable Scenarios for the Greedy Algorithm¶
In the change-making problem, the greedy algorithm works if denominations satisfy “any larger denomination is greater than the sum of all smaller denominations” (e.g., 25, 10, 5, 1: 10+5+1=16 < 25, 5+1=6 < 10, 1 < 5).
Other similar scenarios include:
- Activity scheduling: Select the maximum number of non-overlapping meetings (sort by end time, always choose the earliest-ending activity).
- Huffman coding: Build an optimal prefix code (prioritize merging the least frequent nodes).
Conclusion¶
The core of the greedy algorithm is “local optimality → global optimality”. It is simple and intuitive, and highly efficient for problems where it applies. In the change-making problem, as long as denominations are reasonable, the greedy algorithm quickly finds the minimum number of coins. However, the greedy algorithm does not guarantee optimality for all problems; it only works for problems satisfying the greedy choice property.
Next time you face a problem like “how to complete a task in the fewest steps,” try the greedy idea: start with the largest denomination (or optimal starting point), and at each step choose the best available option. It might just solve the problem efficiently!