Greedy Algorithms: Fundamentals

In the study of algorithms, the greedy algorithm serves as an important strategy frequently employed to solve a specific class of problems. Similar to dynamic programming, greedy algorithms do not necessarily achieve an optimal solution by storing states; instead, they progressively reach a globally optimal solution by making locally optimal choices at each step. In this article, we will delve into the fundamentals of greedy algorithms—including their definition, characteristics, classic application examples—and how to perform greedy selections in concrete problems.

Definition of Greedy Algorithms

A greedy algorithm is a problem-solving strategy that, at each step, selects the option that appears best at that moment, without considering whether this choice leads to a globally optimal solution. In other words, greedy algorithms focus on selecting locally optimal solutions. By consistently making locally optimal decisions, the algorithm hopes to ultimately arrive at a globally optimal solution.

Steps of a Greedy Algorithm

Generally, a greedy algorithm consists of the following steps:

1. Selection Structure: Define the set of feasible choices.
2. Feasibility Check: At each step, verify that the chosen option satisfies all problem constraints—i.e., it remains feasible.
3. Optimization Objective: Evaluate the impact of the current choice according to the optimization goal.
4. Termination Condition: Determine whether a termination condition has been met, indicating whether the current solution qualifies as the final solution.

Characteristics of Greedy Algorithms

The main characteristics of greedy algorithms include:

• Simplicity: Greedy algorithms are typically straightforward to implement and easy to understand.
• Efficiency: For certain problems, greedy algorithms yield solutions with relatively low time complexity.
• Not Always Optimal: Greedy algorithms do not guarantee globally optimal solutions; their applicability is therefore somewhat limited.

Classic Greedy Algorithm Examples

1. Coin Change Problem

Suppose we have coins of various denominations, and our goal is to make change for a given amount using the fewest possible number of coins. Assume coin denominations are 1, 5, 10, and 25. To make change for 30, we proceed as follows:

1. Select the largest denomination coin (25); remaining amount: 5.
2. Select the 5-denomination coin; remaining amount: 0.
3. Change-making completes, using coins 25 and 5.

def coin_change(coins, amount):
    coins.sort(reverse=True)  # Sort in descending order
    count = 0
    for coin in coins:
        while amount >= coin:  # Use as many coins of this denomination as possible
            amount -= coin
            count += 1
    return count

coins = [1, 5, 10, 25]
amount = 30
print(coin_change(coins, amount))  # Output: 2

2. Interval Scheduling Problem

In this problem, we are given a set of activities, each with a start time and an end time. The objective is to select the maximum number of non-overlapping (mutually compatible) activities. We can solve it as follows:

1. Sort all activities by their ending times.
2. Select the first activity, then choose the next activity whose start time does not conflict with the end time of the last selected activity.
3. Repeat until all activities have been considered.

def interval_scheduling(activities):
    # Sort activities by end time
    activities.sort(key=lambda x: x[1])
    last_end_time = 0
    count = 0
    for activity in activities:
        start, end = activity
        if start >= last_end_time:  # If current activity can be selected
            count += 1
            last_end_time = end  # Update latest end time
    return count

activities = [(1, 3), (2, 5), (4, 6), (5, 8)]
print(interval_scheduling(activities))  # Output: 3

Summary

In this article, we explored the fundamentals of greedy algorithms—including their definition, key characteristics, and classic application examples. For certain well-structured problems, greedy algorithms stand out due to their simplicity and efficiency, making them widely adopted in practice. Although greedy algorithms do not always yield globally optimal solutions, they can provide effective and practical solutions when applied appropriately.

In upcoming discussions, we will further examine advanced applications of greedy algorithms and contrast them with dynamic programming—helping us better understand when and why to choose a greedy approach as our problem-solving strategy.