4.2 Greedy Algorithm

1) Greedy Approach

The greedy algorithm is a method where at each step, the locally optimal choice is made in hopes of finding the global optimum. This approach divides the problem into steps and selects the best possible option at each stage. However, this does not guarantee the overall optimal solution.

Greedy algorithms are often used for optimization problems such as minimum spanning trees, knapsack problems, and activity selection.

Applications include:

• Knapsack Problem: Maximize the value of items without exceeding the weight limit.
• Activity Selection: Select non-overlapping activities to maximize the number of events.
• Edit Distance: Find the minimum number of operations required to convert one string into another.
• Network Flow: Determine the maximum flow from source to sink.
• Coin Change: Minimize the number of coins needed for a given amount.

Common Questions:

• Does the greedy algorithm always find the optimal solution? No, it may not, as local choices do not always lead to the global optimum.
• How to determine if a problem can be solved using a greedy approach? If the problem can be decomposed into subproblems with clear optimal solutions, a greedy approach might work.
• What is the time complexity of a greedy algorithm? It depends on the problem size and implemantation, but it typically ranges from O(n log n) to O(n^3).

Examples:

Dijkstra

while (!list.isEmpty()) {
    Vertex curr = chooseMinDistVertex(list);
    updateNeighboursDist(curr);
    list.remove(curr);
    curr.visited = true;
}

• Example where it fails: when negative edges exist, leading to incorrect results.
• Unlike Dijkstra, Bellman-Ford processes all edges repeatedly, ensuring correctness at the cost of efficiency.

Prim

while (!list.isEmpty()) {
    Vertex curr = chooseMinDistVertex(list);
    updateNeighboursDist(curr);
    list.remove(curr);
    curr.visited = true;
}

Kruskal

while (list.size() < size - 1) {
    Edge poll = queue.poll();
    int i = set.find(poll.start);
    int j = set.find(poll.end);
    if (i != j) {
        list.add(poll);
        set.union(i, j);
    }
}

Other examples include:

• Selection sort, heap sort
• Topological sorting
• Union by size and union by height in disjoint sets
• Huffman coding
• Coin change, search keywords like 'change-making problem', 'minimum number of coins'
• Task scheduling
• Approximate solutions for complex problems

2) Coin Change Problem

Number of Ways to Make Change (Leetcode 518)

public class Leetcode518 {
    public int change(int[] coins, int amount) {
        return rec(0, coins, amount, new LinkedList<>(), true);
    }

    public int rec(int index, int[] coins, int remainder, LinkedList<Integer> stack, boolean first) {
        if (!first) {
            stack.push(coins[index]);
        }
        int count = 0;
        if (remainder < 0) {
            print("无解：", stack);
        } else if (remainder == 0) {
            print("有解：", stack);
            count = 1;
        } else {
            for (int i = index; i < coins.length; i++) {
                count += rec(i, coins, remainder - coins[i], stack, false);
            }
        }
        if (!stack.isEmpty()) {
            stack.pop();
        }
        return count;
    }

    private static void print(String prompt, LinkedList<Integer> stack) {
        ArrayList<Integer> print = new ArrayList<>();
        ListIterator<Integer> iterator = stack.listIterator(stack.size());
        while (iterator.hasPrevious()) {
            print.add(iterator.previous());
        }
        System.out.println(prompt + print);
    }

    public static void main(String[] args) {
        Leetcode518 leetcode = new Leetcode518();
        int count = leetcode.change(new int[]{15, 10, 1}, 21);
        System.out.println(count);
    }
}

Optimal Solution (Coin Change) - Brute Force (Leetcode 322)

public class Leetcode322 {
    static int min = -1;

    public int coinChange(int[] coins, int amount) {
        rec(0, coins, amount, new AtomicInteger(-1), new LinkedList<>(), true);
        return min;
    }

    public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack, boolean first) {
        if (!first) {
            stack.push(coins[index]);
        }
        count.incrementAndGet();
        if (remainder == 0) {
            System.out.println(stack);
            if (min == -1) {
                min = count.get();
            } else {
                min = Integer.min(min, count.get());
            }
        } else if (remainder > 0) {
            for (int i = index; i < coins.length; i++) {
                rec(i, coins, remainder - coins[i], count, stack, false);
            }
        }
        count.decrementAndGet();
        if (!stack.isEmpty()) {
            stack.pop();
        }
    }

    public static void main(String[] args) {
        Leetcode322 leetcode = new Leetcode322();
        int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
        System.out.println(count);
    }
}

Optimal Solution (Coin Change) - Greedy (Leetcode 322)

public class Leetcode322 {
    public int coinChange(int[] coins, int amount) {
        int remainder = amount;
        int count = 0;
        for (int coin : coins) {
            while (remainder - coin > 0) {
                remainder -= coin;
                count++;
            }
            if (remainder - coin == 0) {
                remainder = 0;
                count++;
                break;
            }
        }
        if (remainder > 0) {
            return -1;
        } else {
            return count;
        }
    }

    public static void main(String[] args) {
        Leetcode322 leetcode = new Leetcode322();
        int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
        System.out.println(count);
    }
}

3) Huffman Coding Problem

Introduction

Encoding is the process of mapping characters to numbers. For example, ASCII encoding maps 'a' to 0x61. The goal is to minimize the byte usage during transmission.

Huffman coding uses a binary tree structure to ensure prefix-free encoding, allowing efficient compression.

Huffman Tree

public class HuffmanTree {
    static class Node {
        Character ch;
        int freq;
        Node left;
        Node right;
        String code;

        public Node(Character ch) {
            this.ch = ch;
        }

        public Node(int freq, Node left, Node right) {
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        int freq() {
            return freq;
        }

        boolean isLeaf() {
            return left == null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "ch=" + ch +
                    ", freq=" + freq +
                    '}';
        }
    }

    String str;
    Map<Character, Node> map = new HashMap<>();

    public HuffmanTree(String str) {
        this.str = str;
        char[] chars = str.toCharArray();
        for (char c : chars) {
            Node node = map.computeIfAbsent(c, Node::new);
            node.freq++;
        }
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::freq));
        queue.addAll(map.values());
        while (queue.size() >= 2) {
            Node x = queue.poll();
            Node y = queue.poll();
            queue.offer(new Node(x.freq + y.freq, x, y));
        }
        Node root = queue.poll();
        int sum = dfs(root, new StringBuilder());
        for (Node node : map.values()) {
            System.out.println(node + " " + node.code);
        }
        System.out.println("总共会占用 bits:" + sum);
    }

    private int dfs(Node node, StringBuilder code) {
        int sum = 0;
        if (node.isLeaf()) {
            node.code = code.toString();
            sum = node.freq * code.length();
        } else {
            sum += dfs(node.left, code.append("0"));
            sum += dfs(node.right, code.append("1"));
        }
        if (code.length() > 0) {
            code.deleteCharAt(code.length() - 1);
        }
        return sum;
    }

    public static void main(String[] args) {
        new HuffmanTree("abbccccccc");
    }
}

Huffman Encoding and Decoding

public class HuffmanTree {
    // ... 

    public String encode() {
        char[] chars = str.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            sb.append(map.get(c).code);
        }
        return sb.toString();
    }

    public String decode(String str) {
        char[] chars = str.toCharArray();
        int i = 0;
        StringBuilder sb = new StringBuilder();
        Node node = root;
        while (i < chars.length) {
            if (!node.isLeaf()) {
                if (chars[i] == '0') {
                    node = node.left;
                } else {
                    node = node.right;
                }
                i++;
            }
            if (node.isLeaf()) {
                sb.append(node.ch);
                node = root;
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        HuffmanTree tree = new HuffmanTree("abbccccccc");
        String encoded = tree.encode();
        System.out.println(encoded);
        System.out.println(tree.decode(encoded));
    }
}

Related Problems

Solution

public class Leetcode1167 {
    int connectSticks(int[] sticks) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int stick : sticks) {
            queue.offer(stick);
        }

        int sum = 0;
        while (queue.size() >= 2) {
            Integer x = queue.poll();
            Integer y = queue.poll();
            int c = x + y;
            sum += c;
            queue.offer(c);
        }
        return sum;
    }

    public static void main(String[] args) {
        Leetcode1167 leetcode = new Leetcode1167();
        System.out.println(leetcode.connectSticks(new int[]{1, 8, 3, 5}));
        System.out.println(leetcode.connectSticks(new int[]{2, 4, 3}));
    }
}

4) Activity Selection Problem

public class ActivitySelectionProblem {
    static class Activity {
        int index;
        int start;
        int finish;

        public Activity(int index, int start, int finish) {
            this.index = index;
            this.start = start;
            this.finish = finish;
        }

        @Override
        public String toString() {
            return "Activity(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Activity[] activities = new Activity[]{
                new Activity(0, 1, 3),
                new Activity(1, 2, 4),
                new Activity(2, 3, 5)
        };
        select(activities, activities.length);
    }

    public static void select(Activity[] activities, int n) {
        List<Activity> result = new ArrayList<>();
        int i, j;
        i = 0;
        result.add(activities[i]);
        for (j = 1; j < n; j++) {
            if (activities[j].start >= activities[i].finish) {
                result.add(activities[j]);
                i = j;
            }
        }
        System.out.println(result);
    }
}

Non-overlappping Intervals - Leetcode 435

Solution

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int i, j;
    i = 0;
    int count = 1;
    for (j = 1; j < intervals.length; j++) {
        if (intervals[j][0] >= intervals[i][1]) {
            i = j;
            count++;
        }
    }
    return intervals.length - count;
}

5) Fractional Knapsack Problem

Greedy Approach

public class FractionalKnapsackProblem {
    static class Item {
        int index;
        int weight;
        int value;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        int unitPrice() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 4, 24),
                new Item(1, 8, 160),
                new Item(2, 2, 4000),
                new Item(3, 6, 108),
                new Item(4, 1, 4000),
        };
        select(items, 10);
    }

    static void select(Item[] items, int total) {
        Arrays.sort(items, Comparator.comparingInt(Item::unitPrice).reversed());
        int remainder = total;
        int max = 0;
        for (Item item : items) {
            if (remainder - item.weight > 0) {
                max += item.value;
                remainder -= item.weight;
            } else {
                max += remainder * item.unitPrice();
                break;
            }
        }
        System.out.println("最高价值为：" + max);
    }
}

6) 0-1 Knapsack Problem

Greedy Approach

public class KnapsackProblem {
    static class Item {
        int index;
        int weight;
        int value;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitValue() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(0, 1, 1_000_000),
                new Item(1, 4, 1600),
                new Item(2, 8, 2400),
                new Item(3, 5, 30)
        };
        select(items, 10);
    }

    static void select(Item[] items, int total) {
        Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());
        int max = 0;
        for (Item item : items) {
            System.out.println(item);
            if (total >= item.weight) {
                total -= item.weight;
                max += item.value;
            }
        }
        System.out.println("最大价值是:" + max);
    }
}

Limitations of Greedy Algorithms

7) Set Cover Problem

Set cover problem