發工資囉：C 語言貪婪演算法找零錢最少張數

問題情境

給定多筆薪資金額，僅使用 100、50、10、5、2、1 元面額，求支付所有薪資所需的最少鈔票/硬幣總張數。這是典型的「找零錢」問題，貪婪策略在標準面額下能得最優解。

核心邏輯

對每筆薪資，從大面額到小面額依序取盡可能多的張數（count += amount / denomination），餘數繼續處理下一面額（amount %= denomination）。

關鍵程式碼

#include <stdio.h>

int main() {
    int i, num, a[100], count;

    while (scanf("%d", &num) != EOF && num != 0) {
        count = 0;
        for (i = 0; i < num; i++) scanf("%d", &a[i]);

        for (i = 0; i < num; i++) {
            if (a[i] >= 100) { count += a[i] / 100; a[i] %= 100; }
            if (a[i] >= 50)  { count += a[i] / 50;  a[i] %= 50;  }
            if (a[i] >= 10)  { count += a[i] / 10;  a[i] %= 10;  }
            if (a[i] >= 5)   { count += a[i] / 5;   a[i] %= 5;   }
            if (a[i] >= 2)   { count += a[i] / 2;   a[i] %= 2;   }
            count += a[i]; // 剩餘 1 元
        }
        printf("%d\n", count);
    }
    return 0;
}

為何貪婪可行？

面額系統為標準貨幣系統（每個面額是下一面額的整數倍或符合 canonical coin system 條件），貪婪選擇性質成立。

測試範例