Greedy Algorithms Principles and Techniques

Let's look at a simple example to understand greedy algorithms.

Suppose you have two types of banknotes. One is 1 yuan and the other is 100 yuan. There are unlimited notes of each type. But you can only take 10 notes. How should you pick the notes to get the largest total amount?

You probably will say, that's easy! Of course, just take 10 notes of 100 yuan each. That will be 1000 yuan, which is the best way. If you hesitate, you are not thinking straight.

You are right, but also not quite right.

You are right because this is indeed the best answer.

But you are not correct because this way just shows you want the most money, and you skipped the process of coming up with and optimizing the algorithm. That is not how computer algorithms work.

Now, let's ask the computer way: All algorithms are essentially brute force. Right now, you have not tried all possible ways. So how do you know this is really the best answer?

From an algorithm's view, the problem is to make 10 choices. Each choice can be 1 yuan or 100 yuan. All together, there are $2^{10}$ ways to choose.

So in your head, you should first imagine a binary tree of height 10 that goes through all possible answers. After going through this tree, you can find the best answer.

For example, below is a visual panel showing this recursive tree. Since a tree for 10 choices would be too huge, here is what it looks like for just 3 choices:

If you can imagine this binary tree, you can write the code:

// Define: make n choices, return the maximum amount of money you can get
int findMax(int n) {
    if (n == 0) return 0;
    
    // This time choose 1 yuan, then recursively solve the
    // maximum value of the remaining n - 1 choices
    int result1 = 1 + findMax(n - 1);
    // This time choose 100 yuan, then recursively solve
    // the maximum value of the remaining n - 1 choices
    int result2 = 100 + findMax(n - 1);

    // Return the maximum value of the two choices
    return Math.max(result1, result2);
}

The complexity of this algorithm is the number of nodes in a binary tree, which is exponential and very high. However, by this point, you should have noticed that the value of findMax(n - 1) is always the same. Therefore, 100 + findMax(n - 1) is definitely greater than 1 + findMax(n - 1), allowing for optimization:

// Optimization 1, no need to compare the two choices
int findMax(int n) {
    if (n == 0) return 0;
    int result = 100 + findMax(n - 1);
    return result;
}

// Optimization 2, change recursion to iteration
int findMax(int n) {
    int result = 0;
    for (int i = 0; i < n; i++) {
        result += 100;
    }
    return result;
}

// Optimization 3, calculate the result directly
int findMax(int n) {
    return 100 * n;
}

This is the greedy algorithm, which reduces the complexity from $O(2^n)$ to $O(1)$, a remarkable improvement.

You might think this example is too simple?

In fact, algorithms are inherently simple; they are essentially brute-force methods. What makes them valuable are the various optimization techniques derived from brute-force, often given complex names. Those unfamiliar with these techniques might get misled by the terminology, but fundamentally, there's not much difference—it's all about countering challenges as they arise.

Although the example above is simple, it embodies the essence of the greedy algorithm. Next, we will explore further how to identify the greedy choice property and apply greedy algorithms to solve real-world algorithmic problems.

Greedy Choice Property

Example Problem Practice

Steps for Solving Greedy Algorithm Problems