Course contentsShow
← Computer Science
Lesson 904 of 2,87221. Greedy AlgorithmsFree lesson

The Greedy Choice Property

Understand the greedy choice property: making locally optimal choices leads to a global optimum.

The Greedy Choice Property

You'll learn what makes a locally optimal choice lead to a globally optimal solution.

What Is the Greedy Choice Property?

The greedy choice property states that we can assemble a globally optimal solution by making locally optimal (greedy) choices at each step. In other words, the best choice right now will be part of the best overall solution—you never need to reconsider or backtrack.

This is what separates true greedy problems from others. If picking the immediate best option at every decision point guarantees the best final result, your problem has the greedy choice property.

Understanding Through Analogy

Imagine you're climbing a hill in thick fog. A greedy approach says: "Always step in the direction that goes upward most steeply." For some hills (single peaks), this works perfectly—you'll reach the summit. But if the terrain has multiple peaks, you might climb a small hill and miss the tallest mountain nearby. Hills with one clear summit have the "greedy choice property"; complex terrain does not.

How It Works in Algorithms

When the greedy choice property holds:

  1. You make the best local choice available
  2. You reduce the problem to a smaller subproblem
  3. You repeat until done
  4. The result is optimal—no need to try other options

For example, in Activity Selection, always picking the activity that finishes earliest (greedy choice) leaves maximum room for future activities, guaranteeing the optimal schedule.

Why It Matters

Not all problems have this property! The fractional knapsack has it (take items by value-per-weight ratio), but the 0/1 knapsack does not. Recognizing when greedy choices work is crucial for algorithm design.

Key Takeaway: The greedy choice property means making the locally optimal choice at each step provably leads to a globally optimal solution—no backtracking needed.