What is a Greedy Algorithm: Types and Code Examples

If you’ve ever found yourself tackling optimization problems, you’ve likely heard of the greedy algorithm. It’s a simple yet powerful technique that helps you make decisions by picking the best option at each step, with the goal of solving a problem optimally. However, while greedy algorithm are often efficient, they don’t always guarantee the best solution for every problem. So, understanding when and how to use them is key.

In this article, we’ll take a deep dive into Greedy algorithm, explaining what they are, how they work, when they’re most useful, and most importantly, we’ll go through some hands-on examples with code. By the end of this article, you’ll have a clear understanding of how greedy algorithm work and how to implement them in your own coding problems.

Learn data science courses online from the World’s top Universities and fast-track your career.

What is a Greedy Algorithm?

At its core, a Greedy Algorithm is a problem-solving technique that makes a series of locally optimal choices, hoping that these choices will lead to the globally optimal solution. In simple terms, it makes the best possible choice at each step, without worrying too much about the bigger picture.

Let me give you an example to make this clearer:

Imagine you're at a buffet and your goal is to fill your plate with as much food as possible. A greedy approach would mean that, at each step, you grab the dish that looks the most delicious and fulfilling at that moment, without considering how the other dishes might complement your plate. The idea is to keep making the best choice at each step.

While this sounds like a great approach, it doesn’t always guarantee the best solution, especially in complex problems where the "best choice" at each step may not lead to the best overall outcome.

Must Explore: What are Data Structures & Algorithm

Key Characteristics of Greedy Algorithm

Before we jump into examples, let's cover two key concepts that define a greedy algorithm:

1. Greedy Choice Property: This means that a global optimal solution can be arrived at by selecting the locally optimal choices at each step. In other words, if you make the best decision for the current state, it will lead to the best overall solution.
2. Optimal Substructure: This property means that the problem can be broken down into smaller subproblems that are similar to the original problem. The optimal solution to the problem can be constructed from the optimal solutions of these subproblems. Greedy algorithm take advantage of this by solving smaller subproblems and building up to the overall solution.

Types of Greedy algorithm

Greedy algorithm are not a one-size-fits-all solution. There are different types of greedy algorithm, each suited for different types of problems. Here are some key categories and examples of greedy algorithm:

1. Greedy Algorithm for Optimization Problems

This greedy algorithm is typically used to find the maximum or minimum solution in a problem. Here, the goal is to either maximize or minimize a certain objective function.

• Example: Fractional Knapsack Problem
  In the fractional knapsack problem, you aim to maximize the value in the knapsack, and you can take fractional parts of the items. By choosing items with the highest value-to-weight ratio, the greedy algorithm efficiently maximizes the total value.

2. Greedy Algorithm for Scheduling Problems

In scheduling problems, greedy algorithm are used to select tasks or intervals that maximize or minimize some characteristic, like time or resources.

• Example: Activity Selection Problem
  In this problem, you're given a set of activities with their start and end times, and your goal is to select the maximum number of non-overlapping activities. A greedy approach selects activities that finish earliest, leaving room for more activities.

Also Read: Selection Sort Algorithm in Data Structure: Code, Function & Example

3. Greedy Algorithm for Graph Problems

Many problems in graph theory can be efficiently solved using greedy algorithm. These often involve finding minimal spanning trees, shortest paths, or optimal vertex covers.

• Example: Kruskal’s Algorithm (Minimum Spanning Tree)
  Kruskal’s algorithm is used to find a minimum spanning tree in a weighted, undirected graph. It sorts the edges by weight and adds the smallest edge that doesn’t form a cycle.
• Example: Prim’s Algorithm (Minimum Spanning Tree)
  Similar to Kruskal’s, Prim’s algorithm starts from a specific vertex and grows the spanning tree by repeatedly adding the smallest edge connecting the tree to a vertex not yet in the tree.

4. Greedy for Coding and Compression Problems

Greedy algorithm are also used in problems related to encoding, data compression, and file system organization.

• Example: Huffman Coding
  Huffman coding is used for lossless data compression, where you assign shorter codes to more frequent symbols. Greedy algorithm help create the optimal encoding tree by selecting the least frequent symbols to merge first.

Before strengthening advanced algorithms with upGrad’s Executive PG Program in Machine Learning & AI from IIITB, let us take you through the basics of the greedy algorithm!

When Not to Use a Greedy Algorithm

However, greedy algorithm are not always the best solution. They work well only when the problem has both the optimal substructure and the greedy choice property. If a problem does not have these properties, a greedy approach may lead to a suboptimal solution.

Take the 0/1 Knapsack Problem, for example: you have a set of items, each with a weight and a value, and you need to select a subset of them to maximize the total value without exceeding the weight limit. A greedy algorithm would pick items based on the highest value-to-weight ratio, but this could lead to an incorrect solution, as it doesn't consider the overall combination of items.

In such cases, other approaches like dynamic programming would be more appropriate.

Also Read: Top 50+ DSA Interview and Data Structure Viva Questions and Answers for 2025

Greedy Algorithm Example: Fractional Knapsack Problem

Let’s now move to a concrete example to see how a greedy algorithm works in action. We’ll solve the Fractional Knapsack Problem, a classic example where greedy algorithm shine.

Problem Description:

You’re given a set of items, each with a value and weight, and a knapsack that can hold a maximum weight. The goal is to fill the knapsack to maximize the total value of the items it contains. You can take fractions of items, not just whole ones.

Here’s a Java implementation of the Fractional Knapsack Problem:

import java.util.*;
 
class Item {
int weight;
int value;

// Constructor to initialize weight and value
Item(int weight, int value) {
     this.weight = weight;
     this.value = value;
}
}
 
public class GreedyKnapsack {

// Function to calculate the maximum value we can carry in the knapsack
public static double getMaxValue(Item[] items, int capacity) {
     // Create an array of value-to-weight ratios for sorting
     double[] valuePerWeight = new double[items.length];
    
     for (int i = 0; i < items.length; i++) {
         valuePerWeight[i] = (double) items[i].value / items[i].weight;
     }
    
     // Sort items by value per weight in descending order
     List<Item> itemList = new ArrayList<>(Arrays.asList(items));
     itemList.sort((a, b) -> Double.compare(valuePerWeight[b], valuePerWeight[a]));
    
     double totalValue = 0.0;
    
     for (Item item : itemList) {
         // If the item can fit in the knapsack, take it fully
         if (capacity >= item.weight) {
             capacity -= item.weight;
             totalValue += item.value;
         }
         // If the item cannot fit fully, take the fraction that fits
         else {
             totalValue += item.value * ((double) capacity / item.weight);
             break; // Knapsack is full
            }
     }
    
     return totalValue;
}
 
public static void main(String[] args) {
     Item[] items = {
         new Item(10, 60),
         new Item(20, 100),
         new Item(30, 120)
     };
    
     int capacity = 50;
    
     double maxValue = getMaxValue(items, capacity);
    
     System.out.println("Maximum value in Knapsack = " + maxValue);
}
}

Output:

Maximum value in Knapsack = 240.0

Explanation:

1. Value-to-Weight Ratio: We first calculate the value-to-weight ratio for each item. This ratio helps us determine which item provides the most value for its weight.
2. Sorting: The items are sorted by this ratio in descending order so that we can always pick the most valuable item (in terms of value-to-weight ratio) first.
3. Knapsack Filling: We start filling the knapsack by picking items from the sorted list. If the item can be fully added to the knapsack, we add it. If not, we take the fraction of the item that fits in the remaining space.

This greedy approach ensures we get the maximum possible value in the knapsack.

Conclusion

To wrap up, greedy algorithm are incredibly useful for solving optimization problems, especially when the problem has optimal substructure and the greedy choice property. They are efficient, easy to implement, and work well for problems like the Fractional Knapsack, Activity Selection, and Huffman Coding.

However, they are not always the best solution for every problem. In cases where the greedy approach fails to deliver an optimal solution, other techniques like Dynamic Programming might be more appropriate. Understanding when to use greedy algorithm is crucial to solving problems effectively.

I hope this guide has given you a solid understanding of Greedy algorithm, their types, applications, and how to implement them. Keep experimenting with different problems and using greedy algorithm to optimize solutions, and you’ll see just how powerful this technique can be! Happy coding!

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles