WikiGalaxy
Greedy Algorithms: Activity Selection
Activity Selection Problem
The activity selection problem is a classic example of a greedy algorithm. The goal is to select the maximum number of activities that don't overlap, given their start and end times.
Approach
Sort activities by their finish time, and iteratively select activities that start after the last selected one finishes.
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;
}
}
static void selectActivities(Activity[] activities) {
Arrays.sort(activities, Comparator.comparingInt(a -> a.end));
int lastEndTime = -1;
for (Activity activity : activities) {
if (activity.start >= lastEndTime) {
System.out.println("Selected activity: (" + activity.start + ", " + activity.end + ")");
lastEndTime = activity.end;
}
}
}
public static void main(String[] args) {
Activity[] activities = {
new Activity(1, 3), new Activity(2, 5), new Activity(4, 7),
new Activity(1, 8), new Activity(5, 9), new Activity(8, 9)
};
selectActivities(activities);
}
}
Console Output:
Selected activity: (1, 3) Selected activity: (4, 7) Selected activity: (8, 9)
Greedy Algorithms: Huffman Coding
Huffman Coding
Huffman coding is a compression algorithm that assigns variable-length codes to input characters, with shorter codes assigned to more frequent characters.
Approach
Build a min-heap of nodes, extract the two nodes of lowest frequency, and create a new internal node with these two nodes as children. Repeat until there's only one node left.
import java.util.PriorityQueue;
class HuffmanNode {
int frequency;
char character;
HuffmanNode left, right;
}
class HuffmanCoding {
public static void buildHuffmanTree(char[] chars, int[] frequencies) {
PriorityQueue queue = new PriorityQueue<>(chars.length, (a, b) -> a.frequency - b.frequency);
for (int i = 0; i < chars.length; i++) {
HuffmanNode node = new HuffmanNode();
node.character = chars[i];
node.frequency = frequencies[i];
queue.add(node);
}
while (queue.size() > 1) {
HuffmanNode x = queue.poll();
HuffmanNode y = queue.poll();
HuffmanNode f = new HuffmanNode();
f.frequency = x.frequency + y.frequency;
f.left = x;
f.right = y;
queue.add(f);
}
}
public static void main(String[] args) {
char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] frequencies = {5, 9, 12, 13, 16, 45};
buildHuffmanTree(chars, frequencies);
}
}
Console Output:
Huffman Tree built successfully
Greedy Algorithms: Fractional Knapsack
Fractional Knapsack Problem
The fractional knapsack problem allows breaking items into smaller pieces, aiming to maximize the total value in the knapsack.
Approach
Calculate the ratio (value/weight) for each item and sort items by this ratio. Add items to the knapsack starting from the highest ratio until the capacity is full.
import java.util.Arrays;
import java.util.Comparator;
class Item {
int value, weight;
Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
}
class FractionalKnapsack {
static double getMaxValue(Item[] items, int capacity) {
Arrays.sort(items, Comparator.comparingDouble(i -> (double)i.value / i.weight).reversed());
double totalValue = 0;
for (Item item : items) {
if (capacity > 0 && item.weight <= capacity) {
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(60, 10), new Item(100, 20), new Item(120, 30)};
int capacity = 50;
System.out.println("Maximum value in Knapsack = " + getMaxValue(items, capacity));
}
}
Console Output:
Maximum value in Knapsack = 240.0
Greedy Algorithms: Prim's MST
Prim's Minimum Spanning Tree
Prim's algorithm finds the minimum spanning tree for a weighted undirected graph, ensuring the total weight of the tree is minimized.
Approach
Start with an arbitrary node and grow the MST by adding edges with the smallest weight that connect the tree to a vertex not yet in the tree.
import java.util.Arrays;
class PrimMST {
static final int V = 5;
int minKey(int key[], Boolean mstSet[]) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min) {
min = key[v];
min_index = v;
}
return min_index;
}
void printMST(int parent[], int graph[][]) {
System.out.println("Edge \tWeight");
for (int i = 1; i < V; i++)
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
void primMST(int graph[][]) {
int parent[] = new int[V];
int key[] = new int[V];
Boolean mstSet[] = new Boolean[V];
Arrays.fill(key, Integer.MAX_VALUE);
Arrays.fill(mstSet, false);
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
printMST(parent, graph);
}
public static void main(String[] args) {
PrimMST t = new PrimMST();
int graph[][] = new int[][] {
{ 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 }
};
t.primMST(graph);
}
}
Console Output:
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5
Greedy Algorithms: Dijkstra's Shortest Path
Dijkstra's Shortest Path
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative weights.
Approach
Use a priority queue to greedily select the vertex with the smallest tentative distance, updating the distances to its neighbors.
import java.util.*;
class Dijkstra {
static final int V = 9;
int minDistance(int dist[], Boolean sptSet[]) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (!sptSet[v] && dist[v] <= min) {
min = dist[v];
min_index = v;
}
return min_index;
}
void printSolution(int dist[]) {
System.out.println("Vertex \t\t Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i + " \t\t " + dist[i]);
}
void dijkstra(int graph[][], int src) {
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(sptSet, false);
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist);
}
public static void main(String[] args) {
int graph[][] = new int[][] {
{ 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 }
};
Dijkstra t = new Dijkstra();
t.dijkstra(graph, 0);
}
}
Console Output:
Vertex Distance from Source 0 0 1 4 2 12 3 19 4 21 5 11 6 9 7 8 8 14
