ZeroJudge 解題筆記：t161.硬幣湊零

作者：王一哲
日期：2026年10月30日


ZeroJudge 題目連結：t161.硬幣湊零

解題想法

每組測資第一列為兩個整數 $d ~(1 \leq d \leq 6), x ~(0 \leq x \leq 10^5)$，代表有 $d$ 種面額的硬幣，目標金額為 $x$；第二列有 $d$ 個正整數 $c_i ~(1 \leq c_i \leq 1000)$，分別代表第 $i$ 種硬幣的面額。如果要湊出 $x$ 最少需要幾枚硬幣。

這題是標準的無限背包問題。定義最大數量為目標值加 $1$，$maxn = target + 1$，因為這題即使全部用 1 元硬幣湊出目標值 $target$ 也只需要 $target$ 枚硬幣。開一個長度為 $maxn$、預設值皆為 $maxn$ 的一維陣列 $dp$，$dp[i]$ 代表總金額 $i$ 需要的最少硬幣數量。初始值 $dp[0] = 0$，因為金額 0 不需要硬幣。再用兩層 for 迴圈更新 $dp$，外層 for 迴圈跑硬幣面額，內層 for 迴圈由小到大跑總金額。如果最後 $dp[target] == maxn$，代表無法湊出 $target$，輸出 $-1$；反之輸出 $dp[target]$。測試後發現這題是單筆測資，不過寫成處理多筆測資的版本也能 AC。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 13.4 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        target = int(data[ptr + 1])
        ptr += 2
        coins = tuple(map(int, data[ptr : ptr + n]))
        ptr += n

        # 無限背包
        maxn = target + 1
        dp = [maxn] * maxn
        dp[0] = 0
        for coin in coins:
            for j in range(coin, target + 1):
                if dp[j - coin] < maxn:
                   dp[j] = min(dp[j], dp[j - coin] + 1)
        result.append(f"{dp[target]:d}\n" if dp[target] < maxn else "-1\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

使用時間約為 0.2 s，記憶體約為 13.2 MB，通過測試。

n, target = map(int, input().split())
coins = tuple(map(int, input().split()))
maxn = target + 1

dp = [maxn] * maxn
dp[0] = 0
for coin in coins:
    for j in range(coin, target + 1):
       if dp[j - coin] < maxn:
           dp[j] = min(dp[j], dp[j - coin] + 1)

print(dp[target] if dp[target] < maxn else -1)

C++ 程式碼

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

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, target;  // n 種硬幣，目標金額 target
    cin >> n >> target;
    int maxn = target + 1;  // 最大數量
    vector<int> dp (maxn, maxn);  // 無限背包問題，長度 maxn，預設為 maxn
    dp[0] = 0;  // 金額 0 不需要硬幣
    for(int i = 0; i < n; i++) {  // 讀取 n 種硬幣
        int coin;  // 硬幣面額
        cin >> coin;
        for(int j = coin; j <= target; j++) {
            if (dp[j - coin] < maxn) {
                dp[j] = min(dp[j], dp[j - coin] + 1);
            }
        }
    }
    cout << (dp[target] < maxn ? dp[target] : -1) << "\n";
    return 0;
}

C 語言程式碼

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

#include <stdio.h>

int main() {
    int n, target;  // n 種硬幣，目標金額 target
    scanf("%d %d", &n, &target);
    int maxn = 100001;  // 最大數量
    int dp[100001];  // 無限背包問題，長度 100001，預設為 100001
    dp[0] = 0;  // 金額 0 不需要硬幣
    for(int i = 1; i <= 100000; i++) {
        dp[i] = 100001;
    }
    
    for(int i = 0; i < n; i++) {  // 讀取 n 種硬幣
        int coin;  // 硬幣面額
        scanf("%d", &coin);
        for(int j = coin; j <= target; j++) {
            if (dp[j - coin] < maxn) {
                if (dp[j - coin] + 1 < dp[j]) {
                    dp[j] = dp[j - coin] + 1;
                }
            }
        }
    }
    
    if (dp[target] < 100001) {
        printf("%d\n", dp[target]);
    } else {
        puts("-1");
    }
    return 0;
}