ZeroJudge 解題筆記：d904.換零錢

作者：王一哲
日期：2026年8月27日


ZeroJudge 題目連結：d904.換零錢

解題想法

無限背包問題。硬幣的面額存入陣列 $coins$，不需要排序。假設總金額為 $c$，開一個長度為 $c + 1$ 的一維陣列 $dp$，$dp[i]$ 代表總金額為 $i$ 需要的硬幣最少數量。由於題目的金額上限為 $1000$、面額最小值為 $1$，所以硬幣數量的上限為 $1000$，所以建立 $dp$ 陣列時，可以指定長度為 $1001$，預設值皆為超過上限的 $100000$，不需要使用 INT_MAX 或是 float('inf')。

Python 程式碼

使用時間約為 13 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        c = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        coins = tuple(map(int, data[ptr : ptr + n]))
        ptr += n
        # 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        dp = [float('inf')] * (c+1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, c + 1):
                if dp[j - coin] != float('inf'):
                    dp[j] = min(dp[j], dp[j - coin] + 1)
        result.append(f"{dp[c]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 12 ms，記憶體約為 9.6 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        c = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        coins = tuple(map(int, data[ptr : ptr + n]))
        ptr += n
        # 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        dp = [10000] * (c+1)  # 不要用 float('inf')，改成超過題目上限 1000 的數字
        dp[0] = 0
        for coin in coins:
            for j in range(coin, c + 1):
                if dp[j - coin] != 100000 and dp[j - coin] + 1 < dp[j]:
                    # 不要用 min，速度會快一點
                    dp[j] = dp[j - coin] + 1
        result.append(f"{dp[c]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 2 ms，記憶體約為 3.9 MB，通過測試。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int c, n;
    while(scanf("%d %d", &c, &n) != EOF) {
        vector<int> coins (n);
        for(int i = 0; i < n; i++) {
            scanf("%d", &coins[i]);
        }
        // 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        vector<int> dp (c+1, 10000);  // 設定成超過題目上限 1000 的數字
        dp[0] = 0;  // 初始化，總金額 0 硬幣數量 0
        for(int coin : coins) {
            for(int j = coin; j <= c; j++) {
                if (dp[j - coin] != 100000 && dp[j - coin] + 1 < dp[j]) {
                    // 不要用 min，速度會快一點
                    dp[j] = dp[j - coin] + 1;
                }
            }
        }
        printf("%d\n", dp[c]);
    }
    return 0;
}

使用時間約為 1 ms，記憶體約為 1.6 MB，通過測試。

#include <cstdio>

int main() {
    int c, n;
    while(scanf("%d %d", &c, &n) != EOF) {
        int coins[11] = {0};  // 題目硬幣種類上限 10
        for(int i = 0; i < n; i++) {
            scanf("%d", &coins[i]);
        }
        // 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        int dp[1001] = {0};  // 設定成超過題目上限 1000 的數字
        for(int i = 1; i <= 1000; i++) {
            dp[i] = 100000;
        }
        for(int i = 0; i < n; i++) {
            int coin = coins[i];
            for(int j = coin; j <= c; j++) {
                if (dp[j - coin] != 100000 && dp[j - coin] + 1 < dp[j]) {
                    // 不要用 min，速度會快一點
                    dp[j] = dp[j - coin] + 1;
                }
            }
        }
        printf("%d\n", dp[c]);
    }
    return 0;
}

C 語言程式碼

使用時間約為 1 ms，記憶體約為 1.5 MB，通過測試。

#include <stdio.h>

int main() {
    int c, n;
    while(scanf("%d %d", &c, &n) != EOF) {
        int coins[11] = {0};  // 題目硬幣種類上限 10
        for(int i = 0; i < n; i++) {
            scanf("%d", &coins[i]);
        }
        // 無限背包問題，dp[i] 代表總金額 i 的最少硬幣數量
        int dp[1001] = {0};  // 設定成超過題目上限 1000 的數字
        for(int i = 1; i <= 1000; i++) {
            dp[i] = 100000;
        }
        for(int i = 0; i < n; i++) {
            int coin = coins[i];
            for(int j = coin; j <= c; j++) {
                if (dp[j - coin] != 100000 && dp[j - coin] + 1 < dp[j]) {
                    // 不要用 min，速度會快一點
                    dp[j] = dp[j - coin] + 1;
                }
            }
        }
        printf("%d\n", dp[c]);
    }
    return 0;
}