Committing without looking back
A greedy algorithm builds a solution one step at a time, always taking the option that looks best right now and never reconsidering. This only produces an optimal answer for certain problems. The condition that makes it work is the greedy choice property.
What the property says
A problem has the greedy choice property when some globally optimal solution contains the locally optimal choice made at the first step. If that holds, you can safely commit to the greedy pick, remove what it covers, and solve the smaller remaining problem the same way.
- The choice depends only on what is best now, not on solutions to subproblems.
- After committing, the problem reduces to one independent subproblem.
How it is usually proven
The standard proof is an exchange argument: take any optimal solution, then show you can swap one of its choices for the greedy choice without making the solution worse. Repeating the swap transforms the optimal solution into the greedy one. Activity selection by earliest finish time and Huffman coding both satisfy this property; the knapsack problem with whole items does not.
Key idea
The greedy choice property holds when a locally optimal pick is always part of some globally optimal solution, letting a greedy algorithm commit step by step without backtracking.