Greedy Algorithms
An algorithmic paradigm that follows the problem solving approach of making the locally optimal choice at each stage with the hope of finding a global optimum.
A greedy algorithm makes the locally best choice at each step and never reconsiders. It commits to a decision and moves on — no undo, no exploration of alternatives.
It contrast with backtracking, that tries every possible combination
Example
- Given a monetary amount (35 dollars) find the minimum number of bills necessary to pay someone this amount having a $20, $10, $5 and $1 bills
A solution would not be found if there are no $1 bills