en/docs/chapter_greedy/greedy_algorithm.md
<u>Greedy algorithm</u> is a common algorithm for solving optimization problems. Its basic idea is to make the seemingly best choice at each decision stage of the problem, that is, to greedily make locally optimal decisions in hopes of obtaining a globally optimal solution. Greedy algorithms are simple and efficient, and are widely applied in many practical problems.
Greedy algorithms and dynamic programming are both commonly used to solve optimization problems. They share some similarities, such as both relying on the optimal substructure property, but they work differently.
We will first understand how greedy algorithms work through the example problem "coin change". This problem has already been introduced in the "Complete Knapsack Problem" chapter, so I believe you are not unfamiliar with it.
!!! question
Given $n$ types of coins, where the denomination of the $i$-th type of coin is $coins[i - 1]$, and the target amount is $amt$, with each type of coin available for repeated selection, what is the minimum number of coins needed to make up the target amount? If it is impossible to make up the target amount, return $-1$.
The greedy strategy adopted for this problem is shown in the figure below. Given a target amount, we greedily select the coin that is not greater than and closest to it, and continuously repeat this step until the target amount is reached.
The implementation code is as follows:
[file]{coin_change_greedy}-[class]{}-[func]{coin_change_greedy}
You might exclaim: So clean! The greedy algorithm solves the coin change problem in about ten lines of code.
Greedy algorithms are not only straightforward and simple to implement, but are also usually very efficient. In the code above, if the smallest coin denomination is $\min(coins)$, the greedy choice loops at most $amt / \min(coins)$ times, giving a time complexity of $O(amt / \min(coins))$. This is an order of magnitude smaller than the time complexity of the dynamic programming solution $O(n \times amt)$.
However, for certain coin denomination combinations, greedy algorithms cannot find the optimal solution. The figure below provides two examples.
In other words, for the coin change problem, greedy algorithms cannot guarantee finding the global optimal solution, and may even find very poor solutions. It is better suited for solving with dynamic programming.
Generally, the applicability of greedy algorithms falls into the following two situations.
So the question arises: what kind of problems are suitable for solving with greedy algorithms? Or in other words, under what conditions can greedy algorithms guarantee finding the optimal solution?
Compared to dynamic programming, the conditions for using greedy algorithms are stricter, mainly focusing on two properties of the problem.
Optimal substructure has already been introduced in the "Dynamic Programming" chapter, so we won't elaborate on it here. It's worth noting that the optimal substructure of some problems is not obvious, but they can still be solved using greedy algorithms.
We mainly explore methods for determining the greedy choice property. Although its description seems relatively simple, in practice, for many problems, proving the greedy choice property is not easy.
For example, in the coin change problem, although we can easily provide counterexamples to disprove the greedy choice property, proving it is quite difficult. If asked: what conditions must a coin combination satisfy to be solvable using a greedy algorithm? We often can only rely on intuition or examples to give an ambiguous answer, and find it difficult to provide a rigorous mathematical proof.
!!! quote
There is a paper that presents an algorithm with $O(n^3)$ time complexity for determining whether a coin combination can use a greedy algorithm to find the optimal solution for any amount.
Pearson, D. A polynomial-time algorithm for the change-making problem[J]. Operations Research Letters, 2005, 33(3): 231-234.
The problem-solving process for greedy problems can generally be divided into the following three steps.
Determining the greedy strategy is the core step in solving the problem, but it may not be easy to implement, mainly for the following reasons.
To ensure correctness, we should rigorously mathematically prove the greedy strategy, usually using proof by contradiction or mathematical induction.
However, correctness proofs may also not be easy. If we have no clue, we usually choose to debug the code based on test cases, step by step modifying and verifying the greedy strategy.
Greedy algorithms are often applied to optimization problems that satisfy greedy choice property and optimal substructure. Below are some typical greedy algorithm problems.