Mastering Greedy Algorithms: Concepts, Framework, and Classic Problems

1. What Is a Greedy Algorithm

A greedy algorithm makes the locally optimal choice at each step with the hope of finding a global optimum; it focuses on immediate benefit rather than considering the entire problem space. The approach works only when the problem satisfies the greedy‑choice property and optimal substructure, and it is not guaranteed to produce the optimal solution for every problem.

2. Basic Greedy Strategy

The typical steps are:

Formulate a mathematical model of the problem.

Divide the problem into sub‑problems using a divide‑and‑conquer mindset.

Solve each sub‑problem to obtain a local optimum.

Combine the local optima into a solution for the original problem.

3. Problems Suitable for Greedy

A problem is amenable to a greedy solution when it exhibits two key properties:

Greedy‑choice property: an optimal global solution can be constructed by making a locally optimal (greedy) choice.

Optimal substructure: the optimal solution to the whole problem contains optimal solutions to its sub‑problems.

4. Greedy Algorithm Framework

while (can move toward the overall goal) {
    // Use the greedy strategy to select one feasible element
}
// Combine all selected elements into a feasible solution

5. Example: Fractional Knapsack Problem

Given a knapsack of capacity M = 180 and seven items that can be divided arbitrarily, the goal is to maximize total value without exceeding the capacity. Three intuitive greedy strategies are examined:

Select the item with the highest absolute value each time.

Select the item with the smallest weight each time.

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

None of these strategies is provably optimal for the fractional knapsack, so a dynamic‑programming solution is preferred. The article provides a complete C++ implementation that computes the value‑to‑weight ratio, repeatedly picks the best remaining item, and tracks the accumulated weight and value.

#include <iostream>
using namespace std;

struct Node {
    float weight;
    float value;
    bool mark;
    char char_mark;
    float pre_weight_value;
};

int main(int argc, char* argv[]) {
    float Weight[7] = {35,30,60,50,40,15,20};
    float Value[7]  = {10,40,30,50,35,40,30};
    Node array[7];
    for (int i=0;i<7;i++) {
        array[i].value = Value[i];
        array[i].weight = Weight[i];
        array[i].char_mark = 65 + i; // 'A' + i
        array[i].mark = false;
        array[i].pre_weight_value = Value[i]/Weight[i];
    }
    // ... (selection loop omitted for brevity) ...
    return 0;
}

6. Common Greedy Problems

Coin change: Given Chinese currency denominations (1, 5, 10, 20, 50, 100), output the minimum number of coins for a requested amount.

Maximum number concatenation: Arrange a set of positive integers to form the largest possible number (e.g., 45634212).

Activity‑selection (interval scheduling): Choose the maximum number of non‑overlapping activities that share a single resource.

Segment covering: Given N line segments on a line, compute the total length covered by their union.

Each problem can be approached with a simple greedy rule, though correctness must be proved for the specific context.

Conclusion

The article provides a concise overview of greedy algorithm fundamentals, demonstrates a concrete C++ implementation for the fractional knapsack, and lists several classic greedy problems for further practice.