HDU 1085 Holding Bin-Laden Captive!：母函數/生成函數求最小不可湊金額

問題描述

有 1元、2元、5元硬幣，數量分別為 num[1], num[2], num[3]。求無法湊出的最小正整數金額。

母函數（生成函數）方法

每種硬幣對應多項式：

• 1元：1 + x + x^2 + ... + x^{num[1]}
• 2元：1 + x^2 + x^4 + ... + x^{2*num[2]}
• 5元：1 + x^5 + x^{10} + ... + x^{5*num[3]}

三多項式相乘，係數非零的項次即為可湊出的金額。從 1 開始掃描，第一個係數為 0 的即為答案。

實現細節：滾動數組卷積

• 最大可能金額 sum = num[1] + 2*num[2] + 5*num[3]。
• 用 c1[] 存儲當前多項式係數，c2[] 存儲下一輪結果。
• 初始 c1[0..num[1]] = 1。
• 對幣值 v = 2, 5：對每個 j，對 k = 0, v, 2v, ... ≤ v*num，c2[j+k] += c1[j]。
• 每輪結束 c1 ← c2, c2 清零。
• 最後掃描 i = 1 .. sum+1（注意 sum+1：若 1..sum 全可湊出，答案為 sum+1）。

完整參考代碼

#include <cstdio>
#include <cstring>
using namespace std;
int c1[8010], c2[8010];
int val[4] = {0, 1, 2, 5};
int num[4];
int main(){
    while(scanf("%d%d%d", &num[1], &num[2], &num[3]) == 3){
        if(num[1]==0 && num[2]==0 && num[3]==0) break;
        int sum = num[1] + 2*num[2] + 5*num[3];
        memset(c1, 0, sizeof(c1));
        memset(c2, 0, sizeof(c2));
        for(int i=0; i<=num[1]; i++) c1[i] = 1;
        for(int coin=2; coin<=3; coin++){
            for(int j=0; j<=sum; j++) if(c1[j]){
                for(int k=0; k+j<=sum && k<=val[coin]*num[coin]; k+=val[coin])
                    c2[j+k] += c1[j];
            }
            for(int j=0; j<=sum; j++) c1[j]=c2[j], c2[j]=0;
        }
        for(int i=1; i<=sum+1; i++){
            if(c1[i]==0){ printf("%d\n", i); break; }
        }
    }
    return 0;
}

替代視角：0-1 背包 / 多重背包

也可視為背包問題：dp[x] 表示能否湊出金額 x。二進制拆分數量轉 0-1 背包，或單調隊列優化多重背包，同樣可解。母函數本質上是多項式乘法，與背包 DP 等價。

總結

HDU 1085 是母函數/生成函數求可達和的經典入門題，滾動數組卷積實現簡潔高效，注意邊界 sum+1 的處理。