General Method

The greedy method suggests that one can devise an algorithm that works in stages, considering one input at a time.At each stage,a decision is made regarding whether a particular input is in an optimal solution. This is done by considering the inputs in an order determined by some selection procedure. If the inclusion of the next input into the partially constructed optimal solution will result in an infeasible solution,then this input is not added to the partial solution.Otherwise,it is added. The selection procedure itself is based on some optimization measure. This measure may be the objective function.In fact, several different optimization measures may be plausible for a given problem.Most of these,however, will result in algorithms that generates suboptimal solutions. This version of the greedy technique is called the subset paradigm.

We can describe the subset paradigm abstractly, but more precisely than above, by considering the control abstraction in Algorithm 1. The function Select selects an input from a[ ] and removes it. The selected input’s value is assigned to x. Feasible is a Boolean-valued function that determines whether x can be included into the solution vector. The function Union combines x with the solution and updates the objective function. The function Greedy describes the essential way that a greedy algorithm will look, once a particular problem is chosen and the functions Select,Feasible,and Union are properly implemented.