Greedy method is a method of choosing a subset of the dataset as the solution set that result in
some profit. Consider a problem having n inputs; we are required to obtain the solution which is a
series of subsets that satisfy some constraints or conditions. Any subset, which satisfies these
constraints, is called a feasible solution. It is required to obtain the feasible solution that maximizes
or minimizes the objective function. This feasible solution finally obtained is called optimal solution.
If one can devise an algorithm that works in stages, considering one input at a time and at each
stage, a decision is taken on whether the data chosen results with an optimal solution or not. If the
inclusion of a particular data results with an optimal solution, then the data is added into the
partial solution set. On the other hand, if the inclusion of that data results with infeasible solution
then the data is eliminated from the solution set.
In general, greedy algorithms have five pillars:
â€¢ A candidate set, from which a solution is created
â€¢ A selection function, which chooses the best candidate to be added to the solution
â€¢ A feasibility function, that is used to determine if a candidate can be used to contribute
to a solution
â€¢ An objective function, which assigns a value to a solution, or a partial solution, and a
solution function, which will indicate when we have discovered a complete solution.
Greedy algorithms produce good solutions on some mathematical problems, but not on
others. Most problems for which they work well have two properties: