Greedy method | Algorithm Techniques

 Advanced Design and Analysis of Algorithm Techniques

Greedy method

Feasible Solution: For solving a particular problem there exists n inputs and we need to obtain a subset that satisfies some constraints. Then any subset that satisfies these constraints is called feasible solution.

Optimal solution: From a set of feasible solutions, particular solution that satisfies or nearly satisfies the objectives of the function such a solution is called optimal solution.

Objective function: A feasible solution that either minimizes or maximizes a given function is called objective function.

Greedy method is popular for obtaining the optimized solutions. The Greedy-technique is a general algorithm design strategy, built on below mentioned elements:

Configurations: Different choices, values to find

Objective function: Some configurations to be either maximized or minimized

Greedy algorithms don’t always yield an optimal solution. But sometimes they do. We will see a problem for which they do. Then we’ll look at some general characteristics of when greedy algorithms give optimal solutions.

Greedy method

General method:

  1. All problems using the greedy method have n inputs and require us to obtain a subset that satisfies some constraints
  2. Any subset that satisfies these constraints is a feasible solution
  3. A feasible solution that either minimizes or maximizes given objective function is an optimal solution

Control Abstraction for divide and conquer method is given below:

Algorithm Greedy(a, n) // a[1:n] contains the n inputs.
solution := EMPTY; // Initialize the solution for (i := 1 to n ) do
x := Select(a);
if feasible(solution, x) then solution := Union(solution, x);
return solution;


Applications in greedy method are:

          1. Knapsack problem
          2. Job sequencing with deadlines
          3. Minimum cost spanning trees
          4. Single source shortest paths
          5. Optimal merge pattern


Topic : Greedy method | Algorithm Techniques


This articel is contributed by Alapati Sai Karthik. If you any mistake in this article please comment below in comment section.In-case any doubt or issue please reach out us by email

Like our facebook page  and instagram Account for new updates and solve topic-wise  psu and gate cse questions


Leave a Reply