Open In App

Greedy Algorithm Tutorial – Examples, Application and Practice Problem

Last Updated : 30 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Greedy Algorithm is defined as a method for solving optimization problems by taking decisions that result in the most evident and immediate benefit irrespective of the final outcome. It works for cases where minimization or maximization leads to the required solution.

Greedy Algorithm

What is Greedy Algorithm?

A greedy algorithm is a problem-solving technique that makes the best local choice at each step in the hope of finding the global optimum solution. It prioritizes immediate benefits over long-term consequences, making decisions based on the current situation without considering future implications. While this approach can be efficient and straightforward, it doesn’t guarantee the best overall outcome for all problems.

However, it’s important to note that not all problems are suitable for greedy algorithms. They work best when the problem exhibits the following properties:

  • Greedy Choice Property: The optimal solution can be constructed by making the best local choice at each step.
  • Optimal Substructure: The optimal solution to the problem contains the optimal solutions to its subproblems.

Characteristics of Greedy Algorithm

Here are the characteristics of a greedy algorithm:

  • Greedy algorithms are simple and easy to implement.
  • They are efficient in terms of time complexity, often providing quick solutions.
  • Greedy algorithms are used for optimization problems where a locally optimal choice leads to a globally optimal solution.
  • These algorithms do not reconsider previous choices, as they make decisions based on current information without looking ahead.
  • Greedy algorithms are suitable for problems for optimal substructure.

These characteristics help to define the nature and usage of greedy algorithms in problem-solving.

Examples of Greedy Algorithm

Several well-known algorithms fall under the category of greedy algorithms. Here are a few examples:

  • Dijkstra’s Algorithm: This algorithm finds the shortest path between two nodes in a graph. It works by repeatedly choosing the shortest edge available from the current node.
  • Kruskal’s Algorithm: This algorithm finds the minimum spanning tree of a graph. It works by repeatedly choosing the edge with the minimum weight that does not create a cycle.
  • Fractional Knapsack Problem: This problem involves selecting items with the highest value-to-weight ratio to fill a knapsack with a limited capacity. The greedy algorithm selects items in decreasing order of their value-to-weight ratio until the knapsack is full.
  • Scheduling and Resource Allocation: The greedy algorithm can be used to schedule jobs or allocate resources in an efficient manner.
  • Coin Change Problem: The greedy algorithm can be used to make change for a given amount with the minimum number of coins, by always choosing the coin with the highest value that is less than the remaining amount to be changed.
  • Huffman Coding: The greedy algorithm can be used to generate a prefix-free code for data compression, by constructing a binary tree in a way that the frequency of each character is taken into consideration.

Why to use Greedy Approach?

Here are some reasons why you might use the Greedy Approach:

  • Simple and easy to understand: The Greedy Approach is straightforward and easy to implement, making it a good choice for beginners.
  • Fast and efficient: It usually finds a solution quickly, making it suitable for problems where time is a constraint.
  • Provides a good enough solution: While not always optimal, the Greedy Approach often finds a solution that is close to the best possible solution.
  • Can be used as a building block for other algorithms: The Greedy Approach can be used as a starting point for developing more complex algorithms.
  • Useful for a variety of problems: The Greedy Approach can be applied to a wide range of optimization problems, including knapsack problems, scheduling problems, and routing problems.

However, it’s important to remember that the Greedy Approach doesn’t always find the optimal solution. There are cases where it can lead to suboptimal solutions. Therefore, it is necessary to carefully consider the problem and the potential drawbacks before using the Greedy Approach.

How does the Greedy Algorithm works?

Greedy Algorithm solve optimization problems by making the best local choice at each step in the hope of finding the global optimum. It’s like taking the best option available at each moment, hoping it will lead to the best overall outcome.

Here’s how it works:

  1. Start with the initial state of the problem. This is the starting point from where you begin making choices.
  2. Evaluate all possible choices you can make from the current state. Consider all the options available at that specific moment.
  3. Choose the option that seems best at that moment, regardless of future consequences. This is the “greedy” part – you take the best option available now, even if it might not be the best in the long run.
  4. Move to the new state based on your chosen option. This becomes your new starting point for the next iteration.
  5. Repeat steps 2-4 until you reach the goal state or no further progress is possible. Keep making the best local choices until you reach the end of the problem or get stuck.. 

Example:

Let’s say you have a set of coins with values {1, 2, 5, 10, 20, 50, 100} and you need to give minimum number of coin to someone change for 36.

The greedy algorithm for making change would work as follows:

  1. Start with the largest coin value that is less than or equal to the amount to be changed. In this case, the largest coin less than 36 is 20.
  2. Subtract the largest coin value from the amount to be changed, and add the coin to the solution. In this case, subtracting 20 from 36 gives 16, and we add a 20 coin to the solution.
  3. Repeat steps 1 and 2 until the amount to be changed becomes 0.

So, using the greedy algorithm, the solution for making change for 36 would be one 20 coins, one 10 coin, one 5 coins and one 1 coin needed.

Note: This is just one example, and other greedy choices could have been made at each step. However, in this case, the greedy approach leads to the optimal solution.

The greedy algorithm is not always the optimal solution for every optimization problem, as shown in the example below.

Graph with weighted vertices

Graph with weighted vertices

  • In the above graph starting from the root node 10 if we greedily select the next node to obtain the most weighted path the next selected node will be 5 that will take the total sum to 15 and the path will end as there is no child of 5 but the path 10 -> 5 is not the maximum weight path.

Greedy Approach fails

  • In order to find the most weighted path all possible path sum must be computed and their path sum must be compared to get the desired result, it is visible that the most weighted path in the above graph is 10 -> 1 -> 30 that gives the path sum 41

Correct Approach

  • In such cases Greedy approach wouldn’t work instead complete paths from root to leaf node has to be considered to get the correct answer i.e. the most weighted path, This can be achieved by recursively checking all the paths and calculating their weight. 

Greedy Algorithm Vs Dynamic Programming

Below are the comparison of Greedy Algorithm and Dynamic Programming based on various criteria:

Criteria Greedy Algorithm Dynamic Programming
Basic Idea Makes the locally optimal choice at each stage Solves subproblems and builds up to the optimal solution
Optimal Solution Not always guaranteed to provide the globally optimal solution Guarantees the globally optimal solution
Time Complexity Typically faster; often linear or polynomial time Usually slower due to solving overlapping subproblems
Space Complexity Requires less memory; often constant or linear space Requires more memory due to storing intermediate results
Subproblems Overlapping Does not handle overlapping subproblems Handles overlapping subproblems efficiently
Examples Finding minimum spanning tree, Huffman coding Matrix chain multiplication, shortest path problems
Applications Used when a greedy choice at each step leads to the globally optimal solution Applied when the problem can be broken down into overlapping subproblems

Applications of Greedy Algorithms:

  • Dijkstra’s shortest path algorithm: Finds the shortest path between two nodes in a graph.
  • Kruskal’s minimum spanning tree algorithm: Finds the minimum spanning tree for a weighted graph.
  • Huffman coding: Creates an optimal prefix code for a set of symbols based on their frequencies.
  • Fractional knapsack problem: Determines the most valuable items to carry in a knapsack with a limited weight capacity.
  • Activity selection problem: Chooses the maximum number of non-overlapping activities from a set of activities.

Advantages of Greedy Algorithms:

  • Simple and easy to understand: Greedy algorithms are often straightforward to implement and reason about.
  • Efficient for certain problems: They can provide optimal solutions for specific problems, like finding the shortest path in a graph with non-negative edge weights.
  • Fast execution time: Greedy algorithms generally have lower time complexity compared to other algorithms for certain problems.
  • Intuitive and easy to explain: The decision-making process in a greedy algorithm is often easy to understand and justify.
  • Can be used as building blocks for more complex algorithms: Greedy algorithms can be combined with other techniques to design more sophisticated algorithms for challenging problems.

Disadvantages of the Greedy Approach:

  • Not always optimal: Greedy algorithms prioritize local optima over global optima, leading to suboptimal solutions in some cases.
  • Difficult to prove optimality: Proving the optimality of a greedy algorithm can be challenging, requiring careful analysis.
  • Sensitive to input order: The order of input data can affect the solution generated by a greedy algorithm.
  • Limited applicability: Greedy algorithms are not suitable for all problems and may not be applicable to problems with complex constraints.

Greedy Algorithm Most Asked Interview Problems:

Some of the popular problems on the Greedy Approach that are widely asked in interviews are:

Problems

Activity Selection Problem

Kruskal’s Minimum Spanning Tree Algorithm

Huffman Coding

Efficient Huffman Coding for Sorted Input

Prim’s Minimum Spanning Tree Algorithm

Prim’s MST for Adjacency List Representation

Dijkstra’s Shortest Path Algorithm

Job Sequencing Problem

Greedy Algorithm to find Minimum number of Coins

K Centers Problem

Connect n ropes with minimum cost

Graph coloring

Fractional Knapsack Problem

Minimize Cash Flow among a given set of friends who have borrowed money from each other

Find minimum time to finish all jobs with given constraints

Find maximum sum possible equal to sum of three stacks

Minimum Number of Platforms Required for a Railway/Bus Station

Frequently Asked Questions on Greedy Algorithm:

1. What is a greedy algorithm?

A greedy algorithm is an algorithm that makes the best local choice at each step in the hope of finding the global optimum solution. It is a heuristic approach, meaning it does not guarantee finding the optimal solution but often provides a good approximation.

2. When should I use a greedy algorithm?

Greedy algorithms are best suited for problems where optimal substructure exists. This means that the optimal solution to the problem can be constructed from the optimal solutions to its subproblems. Examples of problems where greedy algorithms are effective include Dijkstra’s shortest path algorithm, Kruskal’s minimum spanning tree algorithm, and Huffman coding.

3. What are the advantages and disadvantages of greedy algorithms?

Advantages of greedy algorithms:

  • Easy to understand and implement.
  • Often computationally efficient.
  • Can provide good approximate solutions even when the optimal solution is difficult to find.

Disadvantages of greedy algorithms:

  • Do not always guarantee finding the optimal solution.
  • May not be applicable to all problems.

4. What are some examples of greedy algorithms?

Below are some example of greedy algorithms:

  • Dijkstra’s shortest path algorithm
  • Kruskal’s minimum spanning tree algorithm
  • Huffman coding
  • Fractional knapsack problem
  • Activity selection problem

5. Where can I learn more about greedy algorithms?

There are many resources available online and in textbooks to learn more about greedy algorithms. Some good resource to start learning Greedy algorithms are:

  1. GeeksforGeeks
  2. MIT OpenCourseware:

Related Articles:



Previous Article
Next Article

Similar Reads

Difference between Greedy Algorithm and Divide and Conquer Algorithm
Greedy algorithm and divide and conquer algorithm are two common algorithmic paradigms used to solve problems. The main difference between them lies in their approach to solving problems. Greedy Algorithm:The greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage wit
3 min read
Greedy Approximate Algorithm for Set Cover Problem
Given a universe U of n elements, a collection of subsets of U say S = {S1, S2...,Sm} where every subset Si has an associated cost. Find a minimum cost subcollection of S that covers all elements of U. Example: U = {1,2,3,4,5} S = {S1,S2,S3} S1 = {4,1,3}, Cost(S1) = 5 S2 = {2,5}, Cost(S2) = 10 S3 = {1,4,3,2}, Cost(S3) = 3 Output: Minimum cost of se
6 min read
Greedy Approximate Algorithm for K Centers Problem
Given n cities and distances between every pair of cities, select k cities to place warehouses (or ATMs or Cloud Server) such that the maximum distance of a city to a warehouse (or ATM or Cloud Server) is minimized. For example consider the following four cities, 0, 1, 2, and 3, and the distances between them, how to place 2 ATMs among these 4 citi
9 min read
Comparison among Greedy, Divide and Conquer and Dynamic Programming algorithm
Greedy algorithm, divide and conquer algorithm, and dynamic programming algorithm are three common algorithmic paradigms used to solve problems. Here's a comparison among these algorithms: Approach:Greedy algorithm: Makes locally optimal choices at each step with the hope of finding a global optimum.Divide and conquer algorithm: Breaks down a probl
4 min read
Travelling Salesman Problem | Greedy Approach
Given a 2D matrix tsp[][], where each row has the array of distances from that indexed city to all the other cities and -1 denotes that there doesn't exist a path between those two indexed cities. The task is to print minimum cost in TSP cycle.Examples: Input: tsp[][] = {{-1, 10, 15, 20}, {10, -1, 35, 25}, {15, 35, -1, 30}, {20, 25, 30, -1}}; Below
10 min read
Activity Selection Problem | Greedy Algo-1
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 if the problem has the following property: At every step, we can make a choice that lo
15+ min read
Boruvka's algorithm | Greedy Algo-9
We have discussed the following topics on Minimum Spanning Tree.Applications of Minimum Spanning Tree Problem Kruskal’s Minimum Spanning Tree Algorithm Prim’s Minimum Spanning Tree AlgorithmIn this post, Boruvka's algorithm is discussed. Like Prim's and Kruskal's, Boruvka’s algorithm is also a Greedy algorithm. Below is a complete algorithm. 1) Inp
15+ min read
What is Greedy Algorithm in DSA?
A Greedy Algorithm is defined as a problem-solving strategy that makes the locally optimal choice at each step of the algorithm, with the hope that this will lead to a globally optimal solution. In other words, a greedy algorithm always chooses the option that seems the best at the moment, without considering the future consequences or possibilitie
4 min read
Minimum number of subsequences required to convert one string to another using Greedy Algorithm
Given two strings A and B consists of lowercase letters, the task to find the minimum number of subsequence required to form A from B. If it is impossible to form, print -1.Examples: Input: A = "aacbe", B = "aceab" Output: 3 Explanation: The minimum number of subsequences required for creating A from B is "aa", "cb" and "e".Input: A = "geeks", B =
13 min read
Graph Coloring Using Greedy Algorithm
We introduced graph coloring and applications in previous post. As discussed in the previous post, graph coloring is widely used. Unfortunately, there is no efficient algorithm available for coloring a graph with minimum number of colors as the problem is a known NP Complete problem. There are approximate algorithms to solve the problem though. Fol
12 min read