Elements of Greedy Strategy

Not every optimization problem can be solved greedily. Two structural properties must hold for a greedy approach to yield an optimal solution: the Greedy Choice Property and Optimal Substructure.

A globally optimal solution can be assembled by making locally optimal (greedy) choices. At each step, we choose what looks best right now, and we never need to reconsider.

Key test: Can we prove that there is always an optimal solution that includes the greedy choice? This is typically shown by an exchange argument — taking any optimal solution and swapping in the greedy choice without worsening the result.

An optimal solution to the problem contains optimal solutions to subproblems. After making a greedy choice, the remaining subproblem is a smaller instance of the original.

This property is shared with Dynamic Programming. The difference: greedy makes one choice and proceeds forward; DP considers all choices and combines sub-solutions.

The conceptual diagram below contrasts how Greedy and DP approach decision-making. Greedy commits to one path at each fork, while DP explores all paths.

Counterexample — Coin Change: With coins {1, 3, 4}, making change for 6:

• Greedy: 4 + 1 + 1 = 3 coins
• Optimal: 3 + 3 = 2 coins

The greedy choice (largest coin first) fails because there is no greedy choice property for arbitrary coin denominations.

Counterexample — 0/1 Knapsack: Taking the highest-ratio item first can block a more valuable combination. Greedy choice property does not hold when items are indivisible.

1. Cast the problem as one where a greedy choice leaves a single subproblem
2. Prove the greedy choice property (exchange argument)
3. Prove optimal substructure
4. Implement the greedy algorithm
5. Analyze time/space complexity

Greedy algorithms are elegant and efficient when they work. The two pillars — greedy choice property and optimal substructure — are your litmus tests. Always verify both before committing to a greedy approach.