Greedy Algorithms Principles and Techniques

Let's use a simple example to intuitively demonstrate the greedy algorithm.

Suppose there are two types of banknotes, with denominations of 1 yuan and 100 yuan, and each type is available in unlimited quantities. However, you can only choose 10 notes. How should you choose to maximize the total amount?

You might say, isn't it obvious? Choose all 10 as 100-yuan notes, totaling 1000 yuan. That's the optimal strategy. Hesitating even for a second would be foolish.

While you're right, you're also missing something.

You're right because this is indeed the optimal solution, no doubt about it.

You're missing something because this approach reveals a focus on maximizing money (¬‿¬) while skipping over the generation and optimization process of the algorithm, which does not align with computational thinking.

The essence of all algorithms is exhaustive enumeration, as discussed in 一切算法的本质是穷举. You haven't yet enumerated all possible solutions, so how can you claim this is the optimal one?

From an algorithmic perspective, this problem is essentially about making 10 choices, each with two possibilities: 1 yuan and 100 yuan, resulting in $2^{10}$ possible combinations.

Therefore, you should first envision a binary tree with a height of 10 to enumerate all feasible solutions, traverse these solutions, and then determine the optimal solution.

For example, the visualization panel below illustrates this recursive tree. However, due to the large size of the binary tree generated by making 10 choices, only the scenario of making 3 choices is depicted here:

With this binary tree in mind, you should be able to 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
    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.