GREEDY METHOD

           Greedy method is a method of choosing a subset of the data set as the solution set that results 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.

         The general algorithm for the greedy method is

             1) Choose an element e belonging to dataset D.

             2) Check whether e can be included into the solution set S if Yes solution set is 

                    s<- s U e.

             3) Continue until s is filled up or D is exhausted whichever is earlier.