Greedy Algorithms

Core Concept

Greedy algorithms work well for optimization problems where a series of choices must be made. The core idea is simple: make the choice that seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far but not on future choices or all the solutions to the subproblem.

"However, it's important to note that a greedy strategy does not always produce an optimal solution. The key is to prove that the greedy choice is always part of some optimal solution."

When to Use a Greedy Algorithm?

A problem can often be solved by a greedy approach if it has the Greedy Choice Property: a globally optimal solution can be arrived at by making a locally optimal choice. This means that the choice made at each step, combined with the optimal solution to the remaining subproblem, leads to a globally optimal solution. You must be able to prove that the first choice you make will not prevent you from finding the global optimum.

Example: Coin Problem

Problem: Given a set of coin denominations (e.g., {1, 5, 10, 25}) and a target amount, find the minimum number of coins required to make that amount.

Greedy Strategy: Repeatedly take the largest denomination coin that is less than or equal to the remaining amount.

For standard US currency, this greedy strategy works perfectly. However, if the denominations were {1, 3, 4} and the target was 6, the greedy approach would choose 4 + 1 + 1 (3 coins). The optimal solution is 3 + 3 (2 coins). This illustrates that greedy algorithms don't work for all problems. This particular coin problem requires Dynamic Programming for a general solution.

Classic Greedy Problems

1. Activity Selection Problem:

Problem: You are given n activities with their start and finish times. Select the maximum number of non-overlapping activities.

Greedy Strategy: Sort the activities based on their finish times in ascending order. Select the first activity. Then, iterate through the sorted activities and pick the next activity whose start time is greater than or equal to the finish time of the previously selected one.

2. Fractional Knapsack Problem:

Problem: Given weights and values of n items, put these items in a knapsack of a fixed capacity to get the maximum total value. You can break items (take fractions of them).

Greedy Strategy: Calculate the value-to-weight ratio for each item. Sort the items based on this ratio in descending order. Start picking items with the highest ratio until the knapsack is full. If you can't fit a whole item, take a fraction of it to fill the remaining capacity.