Greedy Algorithms:
Greedy algorithms are algorithms in which we make a “greedy” choice. In other words, this is what appears to be the best or optimal choice at each step. It is important to note that greedy algorithms are not always the most efficient solutions.
For a problem to be amenable to a greedy solution it must exhibit two properties:
- The problem can be decomposed into sub-problems such that the optimal solutions to those sub-problems form an optimal solution to the overall problem. (Sometimes referred to as ”optimal substructure.“)
- Making a greedy choice at each step builds toward a solution that is optimal for the whole problem. (Sometimes referred to as ”greedy choice property.“)
A great example problem that satisfies both properties is finding the minimum required coins to break up some amount of dollars. At each step, we can consistently choose the largest available coin and be assured that is the optimal solution.
However it is noteworthy that the reason the above solution is optimal is because of the cent amounts used. If our coin system only has denominations, {1, 20, and 50} then we would have a non-optimal solution to make 60, as that requires one 50 and ten 1’s. The optimal solution is to use three 20’s.