Introduction

Greedy algorithms and dynamic programming are fundamental approaches used to solve optimization problems. While both aim to find the optimal solution, they differ significantly in their approach and application.

Greedy Approach

The greedy method attempts to use the largest denomination possible at each step, which may not always lead to the optimal solution.

public class CoinChangeGreedy {
    public static void main(String[] args) {
        int[] coins = {25, 10, 5, 1};
        int amount = 63;
        int count = 0;
        
        for (int coin : coins) {
            count += amount / coin;
            amount %= coin;
        }
        System.out.println("Coins used: " + count);
    }
}
          

Coins used: 6

Dynamic Programming Approach

Dynamic programming uses a table to store the minimum number of coins needed for each amount, ensuring the optimal solution is found.

import java.util.Arrays;

public class CoinChangeDP {
    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        System.out.println("Coins used: " + dp[amount]);
    }
}
          

Coins used: 2

Greedy Approach

The greedy method selects items based on the highest value-to-weight ratio, which may not always yield the best result.

import java.util.*;

class Item {
    int value, weight;
    Item(int v, int w) { value = v; weight = w; }
}

public class KnapsackGreedy {
    public static void main(String[] args) {
        List items = Arrays.asList(new Item(60, 10), new Item(100, 20), new Item(120, 30));
        int capacity = 50;
        items.sort((a, b) -> Double.compare(b.value / (double) b.weight, a.value / (double) a.weight));
        
        int totalValue = 0;
        for (Item item : items) {
            if (capacity - item.weight >= 0) {
                capacity -= item.weight;
                totalValue += item.value;
            }
        }
        System.out.println("Total Value: " + totalValue);
    }
}
          

Total Value: 220

Dynamic Programming Approach

Dynamic programming builds a matrix to determine the maximum value achievable with the given capacity and items.

public class KnapsackDP {
    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        int n = values.length;
        
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        System.out.println("Total Value: " + dp[n][capacity]);
    }
}
          

Total Value: 220

Greedy Approach

The greedy algorithm selects the activity that finishes earliest and fits within the current schedule.

import java.util.*;

class Activity {
    int start, finish;
    Activity(int s, int f) { start = s; finish = f; }
}

public class ActivitySelectionGreedy {
    public static void main(String[] args) {
        List activities = Arrays.asList(new Activity(1, 4), new Activity(3, 5), new Activity(0, 6), new Activity(5, 7), new Activity(3, 9), new Activity(5, 9), new Activity(6, 10), new Activity(8, 11), new Activity(8, 12), new Activity(2, 14), new Activity(12, 16));
        
        activities.sort(Comparator.comparingInt(a -> a.finish));
        
        int count = 1;
        int lastFinishTime = activities.get(0).finish;
        
        for (int i = 1; i < activities.size(); i++) {
            if (activities.get(i).start >= lastFinishTime) {
                count++;
                lastFinishTime = activities.get(i).finish;
            }
        }
        System.out.println("Maximum number of activities: " + count);
    }
}
          

Maximum number of activities: 4

Dynamic Programming Approach

Dynamic programming efficiently finds the longest increasing subsequence by storing results of subproblems.

public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        int maxLength = Arrays.stream(dp).max().orElse(1);
        System.out.println("Length of LIS: " + maxLength);
    }
}
          

Length of LIS: 4

Greedy Approach

Huffman coding uses a greedy approach to build an optimal prefix code tree for data compression.

import java.util.PriorityQueue;

class HuffmanNode {
    int frequency;
    char data;
    HuffmanNode left, right;
}

class HuffmanCoding {
    public static void main(String[] args) {
        char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' };
        int[] charFreq = { 5, 9, 12, 13, 16, 45 };
        
        PriorityQueue queue = new PriorityQueue<>(charArray.length, (a, b) -> a.frequency - b.frequency);
        
        for (int i = 0; i < charArray.length; i++) {
            HuffmanNode node = new HuffmanNode();
            node.data = charArray[i];
            node.frequency = charFreq[i];
            node.left = null;
            node.right = null;
            queue.add(node);
        }
        
        while (queue.size() > 1) {
            HuffmanNode x = queue.poll();
            HuffmanNode y = queue.poll();
            
            HuffmanNode sum = new HuffmanNode();
            sum.frequency = x.frequency + y.frequency;
            sum.data = '-';
            sum.left = x;
            sum.right = y;
            queue.add(sum);
        }
        
        System.out.println("Huffman Tree built successfully.");
    }
}
          

Huffman Tree built successfully.