Greedy algorithms are a type of algorithmic paradigm that make the optimal choice at each step with the hope of finding the global optimum. They are used to solve optimization problems by making a series of choices, each of which looks the best at the moment.

Example 1: Activity Selection Problem

Problem Statement

Given a set of activities with start and end times, select the maximum number of activities that don't overlap.

Approach

Sort activities by their end times. Select the first activity and then continue selecting the next activity that starts after the previous one ends.


import java.util.Arrays;
import java.util.Comparator;

class ActivitySelection {
  static class Activity {
    int start, end;
    Activity(int start, int end) {
      this.start = start;
      this.end = end;
    }
  }

  public static void main(String[] args) {
    Activity[] activities = {
      new Activity(1, 3), new Activity(2, 4), new Activity(3, 5),
      new Activity(0, 6), new Activity(5, 7), new Activity(8, 9)
    };
    
    Arrays.sort(activities, Comparator.comparingInt(a -> a.end));

    int count = 0;
    int lastEndTime = -1;
    for (Activity activity : activities) {
      if (activity.start >= lastEndTime) {
        count++;
        lastEndTime = activity.end;
      }
    }
    System.out.println("Maximum number of activities: " + count);
  }

Console Output:

Maximum number of activities: 4

Example 2: Fractional Knapsack Problem

Problem Statement

Given weights and values of items, determine the maximum value that can be obtained with a knapsack of capacity W, allowing fractional quantities.

Approach

Calculate the ratio (value/weight) for each item. Sort items by this ratio and add them to the knapsack, taking fractions if necessary.


import java.util.Arrays;
import java.util.Comparator;

class FractionalKnapsack {
  static class Item {
    int weight, value;
    Item(int weight, int value) {
      this.weight = weight;
      this.value = value;
    }
  }

  public static double getMaxValue(Item[] items, int capacity) {
    Arrays.sort(items, (a, b) -> Double.compare((double)b.value / b.weight, (double)a.value / a.weight));
    double totalValue = 0;
    for (Item item : items) {
      if (capacity - item.weight >= 0) {
        capacity -= item.weight;
        totalValue += item.value;
      } else {
        totalValue += item.value * ((double)capacity / item.weight);
        break;
      }
    }
    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);
  }

Console Output:

Maximum value in Knapsack = 240.0

Example 3: Huffman Coding

Problem Statement

Generate a binary prefix code for characters based on their frequencies to minimize the total length of the encoded string.

Approach

Build a min-heap of nodes representing characters. Extract two nodes with the lowest frequency and combine them to form a new node until one node remains.


import java.util.PriorityQueue;

class HuffmanCoding {
  static class Node {
    char ch;
    int freq;
    Node left, right;
    Node(char ch, int freq) {
      this.ch = ch;
      this.freq = freq;
    }
  }

  static void printCodes(Node root, String str) {
    if (root == null) return;
    if (root.ch != '-') System.out.println(root.ch + ": " + str);
    printCodes(root.left, str + "0");
    printCodes(root.right, str + "1");
  }

  public static void main(String[] args) {
    char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
    int[] freq = {5, 9, 12, 13, 16, 45};
    PriorityQueue pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
    for (int i = 0; i < chars.length; i++) {
      pq.add(new Node(chars[i], freq[i]));
    }
    while (pq.size() > 1) {
      Node left = pq.poll();
      Node right = pq.poll();
      Node sum = new Node('-', left.freq + right.freq);
      sum.left = left;
      sum.right = right;
      pq.add(sum);
    }
    printCodes(pq.poll(), "");
  }

Console Output:

f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111

Example 4: Prim's Minimum Spanning Tree

Problem Statement

Find the minimum spanning tree for a connected, undirected graph with weighted edges using Prim's algorithm.

Approach

Start with any vertex and grow the MST by adding the smallest edge that connects a vertex in the MST to a vertex outside the MST.


import java.util.*;

class PrimsMST {
  static class Edge {
    int src, dest, weight;
    Edge(int src, int dest, int weight) {
      this.src = src;
      this.dest = dest;
      this.weight = weight;
    }
  }

  public static void main(String[] args) {
    int V = 5;
    List edges = Arrays.asList(
      new Edge(0, 1, 2), new Edge(0, 3, 6),
      new Edge(1, 2, 3), new Edge(1, 3, 8),
      new Edge(1, 4, 5), new Edge(2, 4, 7),
      new Edge(3, 4, 9)
    );

    boolean[] inMST = new boolean[V];
    int[] key = new int[V];
    Arrays.fill(key, Integer.MAX_VALUE);
    key[0] = 0;
    int[] parent = new int[V];
    parent[0] = -1;

    for (int i = 0; i < V - 1; i++) {
      int u = minKey(key, inMST, V);
      inMST[u] = true;
      for (Edge edge : edges) {
        if (edge.src == u && !inMST[edge.dest] && edge.weight < key[edge.dest]) {
          parent[edge.dest] = u;
          key[edge.dest] = edge.weight;
        }
      }
    }
    printMST(parent, edges);
  }

  static int minKey(int[] key, boolean[] inMST, int V) {
    int min = Integer.MAX_VALUE, minIndex = -1;
    for (int v = 0; v < V; v++) {
      if (!inMST[v] && key[v] < min) {
        min = key[v];
        minIndex = v;
      }
    }
    return minIndex;
  }

  static void printMST(int[] parent, List edges) {
    System.out.println("Edge \tWeight");
    for (int i = 1; i < parent.length; i++) {
      for (Edge edge : edges) {
        if (edge.dest == i && edge.src == parent[i]) {
          System.out.println(edge.src + " - " + edge.dest + "\t" + edge.weight);
        }
      }
    }
  }

Console Output:

Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5

Example 5: Dijkstra's Shortest Path Algorithm

Problem Statement

Find the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights using Dijkstra's algorithm.

Approach

Maintain a set of vertices whose minimum distance from the source is known. Repeatedly add the closest vertex not in this set to the set.


import java.util.*;

class Dijkstra {
  static class Edge {
    int dest, weight;
    Edge(int dest, int weight) {
      this.dest = dest;
      this.weight = weight;
    }
  }

  public static void main(String[] args) {
    int V = 5;
    List[] graph = new ArrayList[V];
    for (int i = 0; i < V; i++) graph[i] = new ArrayList<>();
    graph[0].add(new Edge(1, 9));
    graph[0].add(new Edge(2, 6));
    graph[0].add(new Edge(3, 5));
    graph[0].add(new Edge(4, 3));
    graph[2].add(new Edge(1, 2));
    graph[2].add(new Edge(3, 4));

    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[0] = 0;

    PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(o -> dist[o]));
    pq.add(0);

    while (!pq.isEmpty()) {
      int u = pq.poll();
      for (Edge edge : graph[u]) {
        if (dist[u] + edge.weight < dist[edge.dest]) {
          dist[edge.dest] = dist[u] + edge.weight;
          pq.add(edge.dest);
        }
      }
    }

    System.out.println("Vertex \tDistance from Source");
    for (int i = 0; i < V; i++) {
      System.out.println(i + " \t" + dist[i]);
    }
  }

Console Output:

Vertex Distance from Source
0 0
1 8
2 6
3 5
4 3