HDU 3591 多重背包與完全背包結合：付款找零最小化經手硬幣數

題目大意

有 N 種硬幣，面值 v_i、數量 c_i。NPC 攜帶這些硬幣購買價值 M 物品，可多付再找零。找零硬幣無數量限制（同面值）。求經手硬幣總數（付出 + 找零）最小值。N ≤ 100, M ≤ 10000。

解法：雙 DP

1. 付款 DP (多重背包)：dp1[j] 表示湊出金額 j 的最少硬幣數（受數量限制）。用二進制優化多重背包。
2. 找零 DP (完全背包)：dp2[j] 表示找零金額 j 的最少硬幣數（無限量）。
3. 合併：枚舉支付金額 pay ≥ M，答案 min(dp1[pay] + dp2[pay-M])。

關鍵代碼

// 多重背包二進制拆分
void multiple_pack(int v, int c) {
    if (v*c >= MAXV) { complete_pack(v); return; }
    int k=1;
    while (k < c) { onezero_pack(k*v, k); c-=k; k*=2; }
    if (c>0) onezero_pack(c*v, c);
}

// 完全背包
void complete_pack(int v) {
    for (int i=v; i<=MAXV; i++)
        if (dp2[i-v]!=-1) dp2[i]=min(dp2[i], dp2[i-v]+1);
}

// 主流程
memset(dp1,-1,sizeof(dp1)); dp1[0]=0;
for (i=1;i<=n;i++) multiple_pack(v[i],c[i]);
memset(dp2,-1,sizeof(dp2)); dp2[0]=0;
for (i=1;i<=n;i++) for (j=0;j<=MAXV-v[i];j++)
    if (dp2[j]!=-1) dp2[j+v[i]]=min(dp2[j+v[i]], dp2[j]+1);
int ans=INF;
for (i=M;i<=MAXV;i++) if (dp1[i]!=-1 && dp2[i-M]!=-1) ans=min(ans, dp1[i]+dp2[i-M]);

複雜度

MAXV = 20000（足夠覆蓋）。多重背包 O(N * MAXV * log C)，完全背包 O(N * MAXV)，總體可接受。