貪心算法經典應用：找零錢問題的 C 語言實現與最優解分析

問題背景

在日常生活中，找零錢是一個常見的優化問題。假設我們擁有無限數量的面值為 20、10、5、1 元的硬幣，給定一個找零金額，如何使用最少數量的硬幣完成找零？這正是貪心算法的典型應用場景之一。

貪心策略核心思想

貪心算法在找零時，總是優先選擇當前可用的最大面值硬幣。以找零 25 元為例，演算法會先選 20 元硬幣，剩餘 5 元再選 5 元硬幣，共用 2 枚硬幣；而非 10+10+5 這樣的 3 枚組合。這種「局部最優」的選擇在特定幣制下能導出全域最優解。

C 語言完整實現

#include <stdio.h>

void greedyMoney(int m[], int k, int n);

int main(void) {
    int money[] = {20, 10, 5, 1};
    int k = sizeof(money) / sizeof(money[0]);
    greedyMoney(money, k, 25);
    system("PAUSE");
    return 0;
}

/*
 * m[]: 存放可供找零的面值，需降序排列
 * k: 面值種類數
 * n: 需要找零的金額
 */
void greedyMoney(int m[], int k, int n) {
    int i;
    for (i = 0; i < k; i++) {
        while (n >= m[i] && n > 0) {
            printf("%d ", m[i]);
            n = n - m[i];
        }
    }
    printf("\n");
}

關鍵程式碼解析

• 面值陣列降序排列：確保優先嘗試大面值，這是貪心策略生效的前提。
• 雙層迴圈結構：外層遍歷面值種類，內層 while 迴圈重複使用同一面值，直到無法再使用為止。
• 時間複雜度：O(k + n/max_coin)，極其高效。

貪心算法的局限性：並非總能得最優解

當幣制不具備「標準幣制」性質時，貪心策略可能失效。例如面值為 11、5、1 時找零 15 元：

• 貪心解：11 + 1 + 1 + 1 + 1 = 5 枚
• 最優解：5 + 5 + 5 = 3 枚

這說明貪心算法僅在特定條件下（如中國現行幣制、美國幣制）保證最優。實際工程中需根據具體幣制驗證或改用動態規劃求解通用最優解。

總結與延伸

找零錢問題展示了貪心算法「簡單、高效、但有前提條件」的特點。掌握其適用邊界，對於算法選型至關重要。後續文章將介紹活動安排、背包問題等更多貪心算法經典案例。