WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Activity Selection Problem
Overview:
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.
Greedy Choice:
Select the activity that finishes first. This ensures that the remaining time is available for as many activities as possible.
import java.util.Arrays;
import java.util.Comparator;
class Activity {
int start, end;
Activity(int start, int end) {
this.start = start;
this.end = end;
}
}
public class ActivitySelection {
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)};
Arrays.sort(activities, Comparator.comparingInt(a -> a.end));
int lastEnd = -1;
for (Activity activity : activities) {
if (activity.start >= lastEnd) {
System.out.println("Selected Activity: (" + activity.start + ", " + activity.end + ")");
lastEnd = activity.end;
}
}
}
}
Console Output:
(1, 3)
(3, 5)
(5, 7)
Fractional Knapsack Problem
Overview:
The fractional knapsack problem allows you to take fractions of items to maximize the total value in the knapsack.
Greedy Choice:
Select items based on the highest value-to-weight ratio, allowing fractions to be taken.
import java.util.Arrays;
import java.util.Comparator;
class Item {
int value, weight;
Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
}
public class FractionalKnapsack {
public static void main(String[] args) {
Item[] items = {new Item(60, 10), new Item(100, 20), new Item(120, 30)};
int capacity = 50;
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;
}
}
System.out.println("Total value in knapsack: " + totalValue);
}
}
Console Output:
240.0
Huffman Coding
Overview:
Huffman coding is used for lossless data compression. It assigns variable-length codes to input characters, with shorter codes assigned to more frequent characters.
Greedy Choice:
Build a priority queue of nodes, and repeatedly merge the two nodes with the lowest frequency until one node is left.
import java.util.PriorityQueue;
class HuffmanNode {
int frequency;
char character;
HuffmanNode left, right;
HuffmanNode(int frequency, char character) {
this.frequency = frequency;
this.character = character;
}
}
class HuffmanCoding {
public static void main(String[] args) {
int[] charFreqs = {5, 9, 12, 13, 16, 45};
char[] charArray = {'a', 'b', 'c', 'd', 'e', 'f'};
PriorityQueue queue = new PriorityQueue<>(charFreqs.length, (a, b) -> a.frequency - b.frequency);
for (int i = 0; i < charFreqs.length; i++) {
queue.add(new HuffmanNode(charFreqs[i], charArray[i]));
}
while (queue.size() > 1) {
HuffmanNode left = queue.poll();
HuffmanNode right = queue.poll();
HuffmanNode newNode = new HuffmanNode(left.frequency + right.frequency, '-');
newNode.left = left;
newNode.right = right;
queue.add(newNode);
}
printCodes(queue.poll(), "");
}
private static void printCodes(HuffmanNode root, String code) {
if (root == null) return;
if (root.character != '-') System.out.println(root.character + ": " + code);
printCodes(root.left, code + "0");
printCodes(root.right, code + "1");
}
}
Console Output:
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
Prim's Minimum Spanning Tree
Overview:
Prim's algorithm finds the minimum spanning tree for a weighted undirected graph, ensuring all vertices are connected with the minimum total edge weight.
Greedy Choice:
Start with an arbitrary vertex and grow the spanning tree by adding the minimum weight edge from the tree to a vertex not yet in the tree.
import java.util.*;
class Graph {
private final int vertices;
private final List> adj;
Graph(int vertices) {
this.vertices = vertices;
adj = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adj.add(new ArrayList<>());
}
}
void addEdge(int u, int v, int weight) {
adj.get(u).add(new Edge(v, weight));
adj.get(v).add(new Edge(u, weight));
}
void primMST() {
boolean[] inMST = new boolean[vertices];
PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
pq.add(new Edge(0, 0));
int mstWeight = 0;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
int u = edge.vertex;
if (inMST[u]) continue;
inMST[u] = true;
mstWeight += edge.weight;
for (Edge e : adj.get(u)) {
if (!inMST[e.vertex]) {
pq.add(e);
}
}
}
System.out.println("Total weight of MST: " + mstWeight);
}
static class Edge {
int vertex, weight;
Edge(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}
}
public class PrimAlgorithm {
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 3, 6);
graph.addEdge(1, 2, 3);
graph.addEdge(1, 3, 8);
graph.addEdge(1, 4, 5);
graph.addEdge(2, 4, 7);
graph.addEdge(3, 4, 9);
graph.primMST();
}
}
Console Output:
Total weight of MST: 16
Kruskal's Minimum Spanning Tree
Overview:
Kruskal's algorithm finds the minimum spanning tree by sorting all edges and adding them one by one, ensuring no cycles are formed.
Greedy Choice:
Add edges in increasing order of their weight, ensuring that no cycle is formed.
import java.util.*;
class KruskalAlgorithm {
static class Edge implements Comparable {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
static class Subset {
int parent, rank;
}
int V, E;
Edge[] edge;
KruskalAlgorithm(int v, int e) {
V = v;
E = e;
edge = new Edge[E];
for (int i = 0; i < e; ++i) {
edge[i] = new Edge();
}
}
int find(Subset[] subsets, int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void union(Subset[] subsets, int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
void KruskalMST() {
Edge[] result = new Edge[V];
int e = 0;
int i = 0;
for (i = 0; i < V; ++i)
result[i] = new Edge();
Arrays.sort(edge);
Subset[] subsets = new Subset[V];
for (i = 0; i < V; ++i)
subsets[i] = new Subset();
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
while (e < V - 1) {
Edge next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
union(subsets, x, y);
}
}
System.out.println("Following are the edges in the constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
}
public static void main(String[] args) {
int V = 4;
int E = 5;
KruskalAlgorithm graph = new KruskalAlgorithm(V, E);
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 10;
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 4;
graph.KruskalMST();
}
}
Console Output:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
