48. Greedy Algorithms: Characteristics and Pitfalls

Greedy algorithms build a solution piece by piece, always choosing the next piece that offers the most obvious, immediate benefit.

Key Characteristics

1. Optimal Substructure: The optimal solution to the problem contains the optimal solution to its subproblems.
2. Greedy Choice Property: A globally optimal solution can be reached by making a locally optimal (greedy) choice at each step.

Pitfalls: When Greed Fails

While simple and fast, a greedy approach does not always lead to a global optimum. It only works if the problem exhibits the Greedy Choice Property.

• Example: Imagine a currency system with denominations {1, 7, 10}. If you need to make 15 cents, a greedy approach might choose 10, then 1, 1, 1, 1, 1 (6 coins). The optimal solution is 7 + 7 + 1 (3 coins).

If the greedy choice is wrong, there is no mechanism to backtrack and correct it.