Greedy Algorithms#
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems.
An optimization problem can be solved using greedy programming if the problem has the following properties:
Greedy choice property
Optimal Substructure
Greedy choice property#
A global optimum can be arrived at by selecting a local optimum
Optimal Substructure#
An optimal solution to the problem contains an optimal solution to subproblems
If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem.
Greedy algorithms are in general more efficient than other techniques like Dynamic Programming, but greedy algorithms cannot always be applied.