Think it through · Start with a story
The robot needs to make 6 yuan using coins worth 1, 3, and 4 yuan. It always takes the largest coin and ends up using 4, 1, and 1. The girl uses two 3-yuan coins instead.
Break Down the Process
- Greedy choiceTake 4 first
- 2 remainsTake 1 and 1
- 3 coins totalNot the fewest
- Another way3 plus 3 uses only 2 coins
A greedy algorithm makes the choice that seems best at the current step.
For some problems, we can prove that this leads to the global optimum; for others, it does not. This coin example shows that taking the biggest option now does not always minimize the total number of coins.
01What Is a Greedy Algorithm?
The basic idea of a greedy algorithm is to choose an option that looks best according to a specific rule at each step, then continue.
02Does “Best Right Now” Always Mean the Largest?
No. A greedy rule might be:
- Choose the activity that ends earliest.
- Choose the feasible edge with the lowest cost.
- Choose the object with the highest current value.
The right choice depends on the problem.
03An Intuitive Example: Scheduling Activities
If the goal is to schedule as many non-overlapping activities as possible in one classroom, a classic correct greedy strategy is:
This leaves as much time as possible for the activities that come afterward.
04Why Is Intuition Alone Not Enough?
In some problems, a locally best choice does not lead to the globally best result.
For some coin systems, for example, taking the largest coin each time may not use the fewest coins overall.
05How Can You Tell Whether a Greedy Rule Might Work?
You will learn formal proof techniques later. For now, ask:
Local choice
Why will this choice not make the future worse?
Remaining problem
Is the remaining task still the same kind of problem?
Can solutions be exchanged?
Can another optimal solution be adjusted to include this choice?
06Is Greedy the Same as Dynamic Programming?
No.
A greedy algorithm usually makes a choice without going back to reconsider every possibility. Dynamic programming systematically stores and combines the results of multiple subproblems.
You will compare them in more detail later.
What You Have Learned
- A greedy algorithm makes a local choice at each step according to a rule.
- “Greedy” does not always mean choosing the largest value.
- A local optimum does not necessarily lead to a global optimum.
- A greedy algorithm needs properties and a proof of correctness.
- Greedy is a design strategy, not a fixed code template.
Next: Why Can One Problem Have Different Algorithms?
Your Turn to Try
Does the example above prove that no coin-change problem can be solved greedily?
Have you decided? Open to see the explanation
No. It only disproves the rule “always take the largest coin” for arbitrary denominations. A particular coin system still needs to be analyzed.