Limitations of Greedy Algorithms

Limitations of Greedy Algorithms

Greedy algorithms can solve optimization problems. Compared with other approaches, their main advantage is that they are often efficient and easy to implement, but they also have limitations.

A greedy algorithm cannot guarantee the best solution for every problem because it makes local choices without considering the whole problem. Without the greedy-choice property, local optima may not combine into a global optimum, and may not even be close to it. The 0-1 knapsack and traveling-salesperson problems are examples where a greedy strategy cannot guarantee the best solution.

A greedy approach may be suitable when a real-time solution is needed and an approximate answer is sufficient. If a problem has both the greedy-choice property and optimal substructure, greedy can produce an optimum. Otherwise, the quality of the approximation must be assessed; optimality is not guaranteed.

Coin change

Suppose coins have denominations 1, 5 and 11. For an amount such as 28, which combination uses the fewest coins?

Greedy gives [11, 11, 5, 1], totaling four coins, which is optimal for this amount. But for 15, it gives [11, 1, 1, 1, 1], using five coins, while [5, 5, 5] uses only three. Dynamic programming can find an optimal coin-change solution.

0-1 knapsack

Fractional knapsack can be solved greedily because items can be split: taking the whole item is unnecessary. In 0-1 knapsack, each item is indivisible and must either be taken or left. Greedy does not reliably produce the exact optimum; dynamic programming can solve it.

Suppose the capacity is 8:

A density-first greedy strategy takes items 1 and 2, leaving 8 − 2 − 3 = 3 capacity. Items 3 and 4 cannot be split and no longer fit. Total value is 3 + 4 = 7.

Dynamic programming finds that items 2 and 4 yield the optimum value of 4 + 6 = 10.