貪心算法簡介
貪心算法是一種在每一步選擇中都采取在當前狀態下最優（局部最優）的選擇，從而希望導致結果是全局最優的算法。貪心算法通常用于解決最優化問題，如最短路徑、最小生成樹、任務調度等。
貪心算法的基本步驟
- 問題分析：明確問題的目標，確定是否可以通過貪心策略解決。
- 選擇貪心策略：設計一個局部最優的選擇標準。
- 證明貪心選擇性質：確保局部最優選擇能導致全局最優解。
- 實現算法：根據貪心策略編寫代碼。
貪心算法的Java實現示例
示例1：找零問題
給定不同面額的硬幣和一個總金額，計算最少需要多少枚硬幣來湊成總金額。
import java.util.Arrays;public class CoinChange {public static int minCoins(int[] coins, int amount) {Arrays.sort(coins); // 排序以便從大到小使用int count = 0;for (int i = coins.length - 1; i >= 0; i--) {while (amount >= coins[i]) {amount -= coins[i];count++;}}return amount == 0 ? count : -1; // 如果無法湊整返回-1}public static void main(String[] args) {int[] coins = {1, 5, 10, 25};int amount = 63;System.out.println("最少硬幣數: " + minCoins(coins, amount));}
}
示例2：活動選擇問題
給定一組活動，每個活動有開始時間和結束時間，選擇盡可能多的互不沖突的活動。
import java.util.ArrayList;
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 ArrayList<Activity> selectActivities(Activity[] activities) {ArrayList<Activity> result = new ArrayList<>();// 按結束時間排序Arrays.sort(activities, Comparator.comparingInt(a -> a.end));result.add(activities[0]);int lastEnd = activities[0].end;for (int i = 1; i < activities.length; i++) {if (activities[i].start >= lastEnd) {result.add(activities[i]);lastEnd = activities[i].end;}}return result;}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(8, 9)};ArrayList<Activity> selected = selectActivities(activities);System.out.println("選擇的活動數量: " + selected.size());}
}
貪心算法的適用條件
- 貪心選擇性質：每一步的局部最優選擇能導致全局最優解。
- 最優子結構：問題的最優解包含子問題的最優解。
貪心算法的局限性
貪心算法并不總是能得到最優解，例如在部分背包問題中，貪心策略可能無法得到全局最優解。因此，在使用貪心算法前，需要驗證其正確性。
總結
貪心算法通過局部最優選擇逐步構建全局最優解，適用于某些特定類型的問題。Java實現時，通常需要排序或優先隊列來輔助選擇。理解貪心算法的適用條件和局限性是正確使用它的關鍵。
)
)
