the greedy-choice property

Imagine you are packing for a trip and, at each moment, you just grab whatever item looks best right now without ever rethinking it. A greedy algorithm works like that: it builds an answer one step at a time, and at every step it commits to the choice that looks best by some simple local rule, never going back. The surprising question is when this shortsighted habit still lands on the truly best overall answer.

The greedy-choice property is the precise condition that makes greed safe: there exists an optimal solution that begins with the locally best (greedy) choice. In other words, you never have to look ahead at the whole problem to make the first move correctly — some best answer agrees with what greed picks first. The usual way to prove this is an exchange argument: take any optimal solution that does not start with the greedy choice, and show you can swap in the greedy choice without making the solution worse, so an optimal solution containing the greedy choice also exists. For example, in scheduling the most jobs in one room, picking the job that finishes earliest is the greedy choice, and you can prove some optimal schedule also starts with that earliest-finishing job.

This property is exactly what separates greedy from dynamic programming. Dynamic programming considers several choices at each step and keeps the best; greedy commits to one choice up front, so it is faster, but it is only correct when the greedy-choice property holds. The honest warning: looking locally best is not the same as being safe. For 0/1 knapsack, grabbing the highest value-per-weight item first looks best but can be wrong, because no exchange argument goes through. Always prove the property before trusting greed.