Java 貪婪算法原理與找零錢問題實現

貪婪算法核心思想

1. 建立數學模型描述問題。
2. 將問題分解為若干子問題。
3. 對每個子問題求局部最優解（貪婪選擇）。
4. 將局部最優解合併為全局一個可行解。

兩大關鍵性質：

• 貪婪選擇性質：全局最優解可通過一系列局部最優選擇得到，不考慮子問題後果。
• 最優子結構性質：問題的最優解包含子問題的最優解。

經典案例：找零錢問題

硬幣面值：25分、10分、5分、1分。目標：用最少硬幣數找零 n 分。

貪婪策略：優先使用最大面值硬幣。

// 找零算法
public static int[] changeCoins(int[] coins, int amount) {
    int[] count = new int[coins.length];
    for (int i = 0; i < coins.length; i++) {
        count[i] = amount / coins[i];
        amount %= coins[i];
    }
    return count;
}

// 測試
public static void main(String[] args) {
    int[] coins = {25, 10, 5, 1};
    int amount = 99;
    int[] result = changeCoins(coins, amount);
    for (int i = 0; i < coins.length; i++) {
        System.out.println(result[i] + " 枚 " + coins[i] + " 分");
    }
}
// 輸出:
// 3 枚 25 分
// 2 枚 10 分
// 0 枚 5 分
// 4 枚 1 分

適用性判斷

並非所有面值組合都適用貪婪策略（如面值 25, 20, 1 找 40 分，貪婪得 25+1×15=16 枚，最優為 20×2=2 枚）。實際應用前需證明貪婪選擇性質成立。

通用伪代碼框架

Greedy(C)  // C 為候選集合
    S = {}   // 解集合
    while not solution(S):
        x = select(C)      // 貪婪選擇
        if feasible(S, x):
            S = S ∪ {x}
            C = C \ {x}
    return S