ZOJ 2734 Exchange Cards：換卡方案數 (母函數/DFS)

問題描述

Mike 想用手中的卡片換取一張價值 n (≤1000) 的卡片。他有 m (≤10) 種卡片，第 i 種價值 val_i，數量 num_i。每種卡片價值不同。求組合總價值恰好為 n 的方案數（順序無關，同種卡片不可超過擁有數量）。多組測試案例，以 EOF 結束，案例間輸出空行。

方法一：母函數 (生成函數)

經典有限背包計數。維護兩個數組 c1、c2，c1[v] 表示當前處理到的卡片種類能組成價值 v 的方案數。初始 c1[0]=1。對每種卡片 (val, num)：

for v = 0..n:
    for k = 0..num, v + k*val ≤ n:
        c2[v + k*val] += c1[v]
swap(c1, c2), clear c2

最終 c1[n] 即答案。時間 O(m * n * max_num)，但 n≤1000, m≤10，實際極快。

方法二：DFS + 剪枝去重

將卡片按價值降序排列。遞歸嘗試每種卡片的使用張數（0 到 num_i）。關鍵去重：同一遞歸層內，若當前卡片價值與前一張相同且前一張未被使用（即 k=0），則跳過，避免產生排列重複。代碼中用 sign 變量標記上一個使用的價值。

參考代碼 (C++ 母函數版)

#include 
#include 
int c1[1010], c2[1010], val[15], num[15];

int main() {
    int n, m, first = 1;
    while (scanf("%d%d", &n, &m) == 2) {
        if (!first) printf("\n");
        first = 0;
        for (int i = 0; i < m; ++i) scanf("%d%d", &val[i], &num[i]);
        memset(c1, 0, sizeof(c1));
        c1[0] = 1;
        for (int i = 0; i < m; ++i) {
            memset(c2, 0, sizeof(c2));
            for (int v = 0; v <= n; ++v) if (c1[v])
                for (int k = 0; k <= num[i] && v + k * val[i] <= n; ++k)
                    c2[v + k * val[i]] += c1[v];
            memcpy(c1, c2, sizeof(c1));
        }
        printf("%d\n", c1[n]);
    }
    return 0;
}

複雜度與選擇

• 母函數：時間 O(m * n * avg_num)，空間 O(n)，代碼簡短、無遞歸風險，推薦。
• DFS：最壞指數級，但數據範圍小通常能過；需仔細去重。

總結

• 有限背包計數問題，母函數是標準高效解法。
• 注意多測試案例間的空行輸出格式。
• 數據範圍小，int 足夠（題目保證答案在整數範圍內）。