Greedy Algorithm

After completing this topic

You will understand the principles of the greedy algorithm, be able to determine when it can be applied, and solve representative problems.

Core Idea

Suppose you need to give 1,260 won in change at a convenience store. You have coins of 500 won, 100 won, 50 won, and 10 won.

Intuitive method: Use the largest coin as much as possible.

python

def coin_change(amount):
    coins = [500, 100, 50, 10]
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count

print(coin_change(1260))  # 6 coins (500×2 + 100×2 + 50×1 + 10×1)

At each step, make the best choice at that moment. Don't look back at the past or anticipate the future. This is the greedy algorithm.

Why "Greedy"?

Characteristics of the greedy algorithm:

Local Optimum: The best choice at the current moment.
No Reversal: Once a choice is made, it is not reversed.
Condition for Guaranteeing Global Optimum: The overall optimal solution is achieved only when certain conditions are met.

In the change-giving problem, choosing the 500 won coin first is intuitively correct. However, this strategy does not work for all problems.

Conditions for a Greedy Algorithm to Work

Two properties are required to guarantee an optimal solution with the greedy algorithm:

Greedy Choice Property

The best choice at each step is included in the overall optimal solution.

In the change-giving example, always using the 500 won coin as much as possible is part of the optimal solution. This is because 500 won = 100 won × 5, so if you don't use the 500 won coin, the number of coins will definitely increase.

Optimal Substructure

The optimal solution to the larger problem includes the optimal solution to the subproblem.

The optimal solution for 1260 won = selecting 2 500 won coins + the optimal solution for 260 won. The remaining 260 won can also be solved using the same strategy.

Cases Where the Greedy Algorithm Fails

If the coins are 400, 300, and 100 won, and you need to give 600 won in change:

python

# Greedy algorithm: 400 + 100 + 100 = 3 coins
# Optimal solution: 300 + 300 = 2 coins

If you choose the 400 won coin first, you must fill the remaining 200 won with two 100 won coins. However, two 300 won coins are better. The strategy of choosing the largest coin first fails.

This is because, like 500, 100, 50, and 10, the larger coins are not an integer multiple of the smaller coins. When this multiple relationship is broken, the greedy algorithm does not guarantee an optimal solution. Dynamic programming (DP) is needed for such problems.

Representative Problem 1: Activity Selection

There is one meeting room, and several meeting requests are received. How can you schedule the maximum number of non-overlapping meetings?

python

def max_meetings(meetings):
    # Sort by ending time
    meetings.sort(key=lambda m: m[1])

    count = 0
    last_end = 0
    for start, end in meetings:
        if start >= last_end:
            count += 1
            last_end = end
    return count

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))  # 4 meetings

Greedy Strategy: Select the meeting that ends the earliest.

Why is this optimal? By selecting meetings that end early, you leave more time remaining, allowing you to schedule more meetings. The greedy choice property is mathematically proven for this problem.

Representative Problem 2: Fractional Knapsack

A knapsack has a capacity of 50 kg, and you can divide items and put them in the knapsack to maximize the value.

python

def fractional_knapsack(capacity, items):
    # Sort in descending order by weight-to-value ratio
    items.sort(key=lambda x: x[1] / x[0], reverse=True)

    total_value = 0
    for weight, value in items:
        if capacity >= weight:
            total_value += value
            capacity -= weight
        else:
            total_value += value * (capacity / weight)
            break
    return total_value

items = [(10, 60), (20, 100), (30, 120)]  # (weight, value)
print(fractional_knapsack(50, items))  # 240.0

Greedy Strategy: Put in the items with the highest value-to-weight ratio (cost-effectiveness) first.

Note: In the 0-1 knapsack problem, where items cannot be divided, the greedy algorithm does not guarantee an optimal solution. The 0-1 knapsack problem should be solved with DP.