What Is Greedy Algorithm

Description:

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.[1] In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.[2]

For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: “At each step of the journey, visit the nearest unvisited city.” This heuristic does not intend to find the best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps.[3]

In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids and give constant-factor approximations to optimization problems with the submodular structure.

Key: The greedy algorithm does not always provide the optimal solution for every problem; the key lies in the choice of the greedy strategy.

The greedy algorithm generally follows the steps below:

• Establish a mathematical model to describe the problem.
• Divide the problem to be solved into several sub-problems.
• Solve each sub-problem to obtain the local optimal solution of the sub-problems.
• Combine the local optimal solutions of the sub-problems to form a solution to the original problems.

Specifics

Property

The key feature that defines a greedy algorithm is its ability to make locally optimal choices at each step without reconsidering previous decisions. This property guarantees that:

• Local decisions lead to global optimum: The best choice at the current stage will be part of the overall optimal solution.

• No backtracking: Once a decision is made, it is never revoked.

Example: In the Fractional Knapsack Problem, always selecting the item with the highest value-to-weight ratio at each step yields the globally optimal solution.

Optimal Substructure

A problem must have an optimal substructure for greedy algorithms to work:

• The optimal solution to the entire problem can be constructed from optimal solutions to its subproblems.

• This property overlaps with dynamic programming but differs in that greedy algorithms don’t revisit subproblems.

Example: In Dijkstra’s Algorithm, the shortest path from node A to C via B combines the shortest path (A→B) with the optimal local choice (B→C).

Correctness Proofs

There are two ways to prove the greedy algorithm: proof by contradiction and induction

Generally, only one of these methods will be used to prove a problem.

Proof by Contradiction: If the answer does not get better after exchanging any two elements / two adjacent elements in the solution, then it can be inferred that the current solution is the optimal solution.

Proof by Induction: First calculate the optimal solution $F_1$ for the boundary case (for example, $n = 1$), and then prove that for each $n$, $F_n + 1$ can be derived from $F_n$.

Example

1. Change-making Problem

This problem is quit common in our daily lives, suppose we have c0, c1, c2, c3, c4, c5, c6 pieces of currently notes of 1dollar, 2dollars, 5dollars, 10dollars, 50dollars and 100dollars respectively. Now, we need to pay K dollars with this money; What is the minimum number of paper money required?

Using the idea of the greedy algorithm, it’s obvious that at each step we should use the largest denomination of currency possible.

In our daily life, we naturally do this as well.

#include <iostream>
#include <algorithm> 
using namespace std;

const int N = 6; 
int denominations[N] = {1, 2, 5, 10, 50, 100}; 
int available_bills[N] = {2, 5, 10, 30, 4, 19}; 
int used_bills[N] = {0}; 

bool make_change(int amount) {
    if(amount < 0) return false;
    
    for(int i = N-1; i >= 0; i--) {
        used_bills[i] = min(available_bills[i], amount / denominations[i]);
        amount -= used_bills[i] * denominations[i];
    }
    return amount == 0; 
}

int main() {
    int amount;
    cout << "Enter the amount to make change for: ";
    cin >> amount;
    
    if(make_change(amount)) {
        cout << "Optimal change using greedy algorithm:" << endl;
        for(int j = N-1; j >= 0; j--) {
            if(used_bills[j] > 0) { 
                cout << "¥" << denominations[j] << " bills: " << used_bills[j] << endl;
            }
        }
    } else {
        cout << "Error: Cannot make exact change" << endl;
        if(amount > 0) {
            cout << "Remaining amount: ¥" << amount << endl;
        }
    }
    return 0;
}

2. Djikstra Algorithm

Dijkstra is a typical shortest path algorithm, an algorithm and idea for calculating the shortest path from a starting node to all other nodes in the path. It is introduced in some professional courses such as data structure, graph theory, and operations research. Its idea is a basic algorithm for finding the shortest path. By changing the basic idea, many complex problems can be solved, such as navigation routes, dynamic programming, etc.

Tips: But, a greedy algorithm never reconsiders its choices. This is the main difference from dynamic programming, which is exhaustive and is guaranteed to find the solution. After every stage, dynamic programming makes decisions based on all the decisions made in the previous stage and may reconsider the previous stage’s algorithmic path to the solution.

The following picture is a multi-node, multi-path graph. The following uses this graph as an example to explain the process of Dijkstra’s algorithm to find the shortest path.

Take point A as the starting point, find the shortest path from point A to the other 5 points B C D E F, and finally get the shortest path from A to the other points.

Because the shortest distance from A to the other 5 points is required, an array is constructed to record the path distance from A to the 5 points B C D E F.

Here is a convention:

• If A can reach the node directly, the path length, i.e. the weight, is used as its distance
• If node A cannot reach the node directly, infinity is used to represent the distance from A to the point.
• The distance from any point to itself is 0

So at the beginning, the distance array from point A to all points in the graph is as followings:

A	B	C	D	E	F
0	10	∞	4	∞	∞

The idea of Dijkstra’s algorithm is to select the nearest point from the above shortest distance array each time, use it as the next point, and then recalculated the distance from the starting point through this point to all other points, and update the shortest distance data. The point that have been selected are the points that determine the shortest path and will not participate in the next calculation.

#include <iostream>
#include <climits>
#include <algorithm>

using namespace std;

const int MAX = INT_MAX;
const int SIZE = 6; 

void dijkstra(int matrix[SIZE][SIZE], int start_node, int distance[SIZE]) {
    bool used_node[SIZE] = {false};
    
    for (int i = 0; i < SIZE; i++) {
        distance[i] = MAX;
    }
    distance[start_node] = 0;
    
    while (true) {
        int min_value = MAX;
        int min_value_index = -1;
        bool all_visited = true;
        
        for (int i = 0; i < SIZE; i++) {
            if (!used_node[i] && distance[i] < min_value) {
                min_value = distance[i];
                min_value_index = i;
                all_visited = false;
            }
        }
        
        if (all_visited || min_value == MAX) {
            break; 
        }
        
        used_node[min_value_index] = true;
        
        for (int i = 0; i < SIZE; i++) {
            if (matrix[min_value_index][i] != MAX) { 
                if (distance[min_value_index] + matrix[min_value_index][i] < distance[i]) {
                    distance[i] = distance[min_value_index] + matrix[min_value_index][i];
                }
            }
        }
    }
}

int main() {
    int matrix[SIZE][SIZE] = {
        {0, 10, MAX, 4, MAX, MAX},
        {10, 0, 8, 2, 6, MAX},
        {MAX, 8, 10, 15, 1, 5},
        {4, 2, 15, 0, 6, MAX},
        {MAX, 6, 1, 6, 0, 12},
        {MAX, MAX, 5, MAX, 12, 0}
    };
    
    int start_node;
    cout << "Enter starting node (0-" << SIZE-1 << "): ";
    cin >> start_node;
    
    int distances[SIZE];
    dijkstra(matrix, start_node, distances);
    
    cout << "Shortest distances from node " << start_node << ": ";
    for (int i = 0; i < SIZE; i++) {
        if (distances[i] == MAX) {
            cout << "INF ";
        } else {
            cout << distances[i] << " ";
        }
    }
    cout << endl;
    return 0;
}

References

[1]. Black, Paul E. (2 February 2005). “greedy algorithm”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology (NIST). Retrieved 17 August 2012.

[2] van Melkebeek, Dieter. “Greedy Approximations” (PDF). University of Wisconsin–Madison. Retrieved 2025-07-25.

[3] Frieze, Alan; Pegden, Wesley (2023-10-05). “The bright side of simple heuristics for the TSP”. arXiv preprint. arXiv:2310.03222. Retrieved 2025-07-25.