杭電 ACM 2021 練習題：找零錢問題的貪心解法

杭電 OJ 經典題目：找零錢最少硬幣數

這是一道典型的貪心算法練習題（杭電 2021 相關練習）。給定金額，使用面額 100、50、10、5、2、1 的硬幣找零，求最少硬幣總數。由於面額系統具有「標準貨幣系統」特性（每個面額都是下一個面額的整數倍或經過驗證的最優組合），貪心策略（優先使用大面額）能保證全域最優解。

題目重述

• 輸入多組測試資料，每組第一行 n 表示查詢次數（n=0 結束）。
• 每查詢一行金額 m（整數）。
• 輸出該組查詢的總硬幣數（所有 m 所需硬幣數之和）。

演算法邏輯

對每個金額 m：

1. 依序嘗試面額 100, 50, 10, 5, 2, 1。
2. 當前面額 coin 可用數量 = m / coin。
3. 累加至總數，更新 m = m % coin。
4. 重複直到 m = 0。

完整代碼（C 語言）

#include <stdio.h>

int main() {
    int n, m, i, total, coin, count;
    int coins[6] = {100, 50, 10, 5, 2, 1};

    while (scanf("%d", &n) != EOF && n != 0) {
        total = 0;
        for (i = 0; i < n; i++) {
            scanf("%d", &m);
            for (int j = 0; j < 6; j++) {
                coin = coins[j];
                count = m / coin;
                total += count;
                m %= coin;
            }
        }
        printf("%d\n", total);
    }
    return 0;
}

關鍵點解析

• 貪心證明：面額集合 {100,50,10,5,2,1} 滿足「標準貨幣系統」條件，任意金額用最大面額優先一定能得到最少硬幣數。若面額為 {100, 50, 20, 10, 5, 2, 1} 則需動態規劃。
• 輸入處理：while (scanf("%d", &n) != EOF && n != 0) 同時處理 EOF 與結束標誌。
• 累加邏輯：題目要求輸出「該組所有查詢的總硬幣數」，故需雙層迴圈累加 total。

複雜度分析

• 時間複雜度：O(n × k)，k=6 為固定面額數，實際為 O(n)。
• 空間複雜度：O(1)，僅使用常數額外空間。

擴展思考

若面額系統改為任意集合（如 {1, 3, 4}），貪心會失效（例：金額 6，貪心給 4+1+1=3 枚，最優為 3+3=2 枚），此時需改用動態規劃（DP）求解最少硬幣數。