Greedy Algorithm: Concepts, Basic Approach, Applicability, and Example Analysis

This article was originally posted on a Facebook blog; click the "Read original" link at the bottom for the full source.

I. Basic Concept

A greedy algorithm makes the locally optimal choice at each step without considering the overall optimal solution. It relies on a greedy strategy that must satisfy the property of "no after‑effect"—future decisions depend only on the current state, not on past choices.

II. Basic Idea of Greedy Algorithms

1. Build a mathematical model of the problem. 2. Decompose the problem into sub‑problems. 3. Solve each sub‑problem to obtain a locally optimal solution. 4. Combine the local optima to form a solution to the original problem.

III. Problems Suitable for Greedy Algorithms

The prerequisite for applying a greedy strategy is that a locally optimal choice leads to a globally optimal solution. In practice such cases are rare; one usually tests a few concrete data instances to judge suitability.

IV. Implementation Framework

Start from an initial solution; then repeatedly improve it:

while (can move toward the overall goal) {
    use a feasible decision to obtain an element of a feasible solution;
}

Finally, combine all obtained elements into a feasible solution for the original problem.

V. Choosing a Greedy Strategy

Because a greedy algorithm can only reach a global optimum through locally optimal decisions, it is essential to verify that the problem satisfies the necessary conditions before adopting a greedy strategy.

VI. Example Analysis

Consider a fractional knapsack problem with capacity M = 150 and seven items:

Items: A B C D E F G Weights: 35 30 60 50 40 10 25 Values: 10 40 30 50 35 40 30

Objective: maximize total value ∑p_i subject to ∑w_i ≤ M .

Three greedy strategies are examined:

Select the item with the highest value.

Select the item with the smallest weight.

Select the item with the highest value‑to‑weight ratio.

All three strategies can fail to produce the optimal solution, as shown by counter‑examples:

(1) Max‑value strategy: with capacity 30, items A(28,30), B(12,20), C(12,20). Greedy picks A (value 30) and cannot add others, while B + C give total value 40.

(2) Min‑weight strategy: similar counter‑example demonstrates sub‑optimality.

(3) Max value‑to‑weight ratio strategy: with capacity 30, items A(28,28), B(20,20), C(10,10) all have the same ratio; choosing A leads to a non‑optimal solution.

These examples illustrate that greedy algorithms are useful only when their strategy can be proven correct; otherwise, they may yield sub‑optimal results.