C語言貪心算法經典：找零錢問題（最少張數）

問題描述

給定 num 筆薪資金額，面額為 100, 50, 10, 5, 2, 1 元。每筆薪資用最少張數找零，輸出總張數。多組測試，num=0 結束。

貪心策略正確性證明

面額集合 {100,50,10,5,2,1} 滿足 標準貨幣系統 性質：每個面額都是下一個面額的整數倍（或組合），貪心選擇當前最大面額必能得到全域最優解。反例：面額 {4,3,1} 找零 6，貪心得 4+1+1 (3張)，最優為 3+3 (2張)。

代碼實現與優化

原始版本（逐面額除模）

count += a[i]/100; a[i] %= 100;
count += a[i]/50;  a[i] %= 50;
... // 重複 6 次

優化版：面額陣列 + 迴圈

#include <stdio.h>

int main() {
    int denominations[6] = {100, 50, 10, 5, 2, 1};
    int num, salary;
    while (scanf("%d", &num) == 1 && num != 0) {
        int total = 0;
        for (int i = 0; i < num; i++) {
            scanf("%d", &salary);
            for (int d = 0; d < 6; d++) {
                total += salary / denominations[d];
                salary %= denominations[d];
            }
        }
        printf("%d\n", total);
    }
    return 0;
}

進階擴展：動態規劃通用找零

若面額不具備貪心性質，需用 DP 求最少硬幣數：

int dp[MAX_AMOUNT+1];
dp[0] = 0;
for (int i = 1; i <= amount; i++) dp[i] = INF;
for (int c = 0; c < n_coins; c++)
    for (int v = coins[c]; v <= amount; v++)
        dp[v] = min(dp[v], dp[v - coins[c]] + 1);

時間 O(n×amount)，空間 O(amount)。

實際應用場景

• 自動販賣機/ATM 找零模組。
• 遊戲背包系統：最少道具合成目標物品。
• 資源調度：最少批次完成訂單。