ZeroJudge 解題筆記：b511. 換銅板

作者：王一哲
日期：2025年7月23日


ZeroJudge 題目連結：b511. 換銅板

解題想法

這題我用函式遞迴窮舉所有面額硬幣、數量、總金額的組合，如果遇到總金額符合題目要求的組合就輸出答案。

Python 程式碼

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

def solve():
    import sys
    n = int(sys.stdin.readline())  # n 種面額
    coins = sorted(list(map(int, sys.stdin.readline().split())))  # 硬幣面額，由小到大排序
    target = int(sys.stdin.readline())  # 目標
    ### 主要的解題過程 ###
    def backtrack(curr, nums, total):
        if total == target:  # 遞迴出口，符合目標
            s = "(" + ",".join(map(str, nums)) + ")"  # 要輸出的字串
            sys.stdout.write(f"{s}\n")
            return
        if curr == n or total > target:  # 遞迴出口，已經到最後一種面額或超過目標
            return
        maxn = (target-total) // coins[curr]  # 這個面額可用的最大數量
        for i in range(maxn+1):  # 依序測試 0 ~ maxn 個
            nums[curr] = i  # 設定這個面額的數量
            backtrack(curr+1, nums, total + coins[curr]*i)  # 遞迴
    ### End of backtrack ###
    backtrack(0, [0]*n, 0)  # 從索引值 0、個數 0、加總 0 開始測試
### End of solve ###

if __name__ == "__main__":
    solve()

如果遞迴時代入的參數值不是由小到大，需要先將答案都儲存起來，排序後再輸出。使用時間約為 19 ms，記憶體約為 3.3 MB，通過測試。

def solve():
    import sys
    n = int(sys.stdin.readline())
    coins = sorted(list(map(int, sys.stdin.readline().split())))
    target = int(sys.stdin.readline())
    ans = []
    ### main ###
    def backtrack(curr, nums, total):
        if total == target:
            ans.append(nums[:])
            return
        if curr == n or total > target:
            return
        maxn = (target-total) // coins[curr]
        for i in range(maxn, -1, -1):
            nums[curr] = i
            backtrack(curr+1, nums, total + coins[curr]*i)
    ### End of backtrack ###
    backtrack(0, [0]*n, 0)
    ans.sort()
    for a in ans:
        s = "(" + ",".join(map(str, a)) + ")\n"
        sys.stdout.write(s)

if __name__ == "__main__":
    solve()

C++ 程式碼

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

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

int n, target;  // n 種面額，目標
vector<int> coins (10);  // 硬幣面額

/* 主要的解題過程 */
void backtrack(int curr, vector<int>& nums, int total) {
    if (total == target) {  // 遞迴出口，符合目標
        printf("(%d,", nums[0]);
        for(int i=1; i<n-1; i++) printf("%d,", nums[i]);
        printf("%d)\n", nums[n-1]);
        return;
    }
    if (curr == n || total > target) {  // 遞迴出口，已經到最後一種面額或超過目標
        return;
    }
    int maxn = (target-total) / coins[curr];  // 這個面額可用的最大數量
    for(int i=0; i<=maxn; i++) {  // 依序測試 0 ~ maxn 個
        nums[curr] = i;  // 設定這個面額的數量
        backtrack(curr+1, nums, total + coins[curr]*i);  // 遞迴
    }
}

int main() {
    scanf("%d", &n);
    coins.resize(n);
    for(int i=0; i<n; i++) scanf("%d", &coins[i]);
    sort(coins.begin(), coins.end());  // 硬幣面額由小到大排序
    scanf("%d", &target);
    vector<int> nums (n, 0);  // 硬幣數量
    backtrack(0, nums, 0);  // 從索引值 0、個數 0、加總 0 開始測試
    return 0;
}