貪心算法是一種在每一步選擇中都采取當前狀態下最優或最優近似的選擇，以期望最終得到全局最優解的算法。貪心算法并不總能得到全局最優解，但在某些問題上，它可以得到全局最優解，并且比動態規劃等其他方法更為簡單和高效。
貪心算法的基本思想
貪心算法的核心思想是：
- 貪心選擇性質：每一步都做出局部最優選擇，即當前最優的選擇，希望通過一系列局部最優選擇能得到全局最優解。
- 無后效性：當前的選擇不會影響后續的選擇，即后面的選擇不依賴于之前的狀態。
貪心算法的應用場景
貪心算法通常用于解決一些優化問題，比如最短路徑問題、背包問題、活動選擇問題、最小生成樹等。下面通過幾個經典問題來介紹貪心算法。
1. 活動選擇問題
問題描述
給定一組活動，每個活動有一個開始時間和結束時間。要求選擇盡可能多的活動，使得這些活動互不沖突。
貪心策略
每次選擇結束時間最早且不與已選活動沖突的活動。
代碼實現
import java.util.Arrays;
import java.util.Comparator;public 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, 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)};Arrays.sort(activities, Comparator.comparingInt(a -> a.end));int count = 1;int endTime = activities[0].end;for (int i = 1; i < activities.length; i++) {if (activities[i].start >= endTime) {count++;endTime = activities[i].end;}}System.out.println("Maximum number of activities: " + count);}
}
2. 0/1 背包問題的貪心近似
問題描述
給定一個容量為 W 的背包和 N 個物品，每個物品有一個重量和價值。要求在不超過背包容量的情況下，選擇若干物品使得這些物品的總價值最大。
貪心策略
按單位價值（價值/重量）從大到小的順序選擇物品，盡量多地選擇高單位價值的物品。
代碼實現
import java.util.Arrays;
import java.util.Comparator;public class FractionalKnapsack {static class Item {int weight;int value;Item(int weight, int value) {this.weight = weight;this.value = value;}}public static void main(String[] args) {Item[] items = {new Item(10, 60),new Item(20, 100),new Item(30, 120)};int capacity = 50;Arrays.sort(items, Comparator.comparingDouble(i -> (double) i.value / i.weight).reversed());double totalValue = 0;int remainingCapacity = capacity;for (Item item : items) {if (item.weight <= remainingCapacity) {totalValue += item.value;remainingCapacity -= item.weight;} else {totalValue += item.value * ((double) remainingCapacity / item.weight);break;}}System.out.println("Maximum value in Knapsack = " + totalValue);}
}
3. 哈夫曼編碼
問題描述
給定一組字符及其出現的頻率，要求構建一棵二叉樹，使得樹的帶權路徑長度最小。帶權路徑長度是所有葉子節點的深度乘以頻率之和。
貪心策略
每次選擇頻率最小的兩個節點合并，直到所有節點合并成一棵樹。
代碼實現
import java.util.PriorityQueue;public class HuffmanCoding {static class Node {int freq;Node left, right;Node(int freq) {this.freq = freq;}}public static void main(String[] args) {int[] frequencies = {5, 9, 12, 13, 16, 45};PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.freq));for (int freq : frequencies) {pq.add(new Node(freq));}while (pq.size() > 1) {Node left = pq.poll();Node right = pq.poll();Node merged = new Node(left.freq + right.freq);merged.left = left;merged.right = right;pq.add(merged);}printCodes(pq.poll(), "");}private static void printCodes(Node root, String code) {if (root.left == null && root.right == null) {System.out.println(root.freq + ": " + code);return;}printCodes(root.left, code + "0");printCodes(root.right, code + "1");}
}
貪心算法的總結
貪心算法通過在每一步選擇中都采取局部最優的選擇，希望最終得到全局最優解。它通常用于解決一些優化問題，如活動選擇問題、背包問題和哈夫曼編碼等。雖然貪心算法不總能得到全局最優解，但在某些特定問題上，它能以簡單和高效的方式得到全局最優解。理解貪心算法的基本思想和應用場景，有助于在實際問題中選擇合適的算法解決方案。
)
