HDU 2079 选课时间：多重背包组合计数

题目大意

有 k 类课程，第 i 类学分为 a[i]，有 b[i] 门可选。求选总学分恰为 n 的组合数（同学分课程视为无差别）。约束：n≤40, k≤8, a≤8, b≤10。

动态规划：多重背包计数

dp[j] 表示凑成学分 j 的组合数。初始 dp[0]=1。对每类课程，做多重背包转移。

三种实现对比

1. 展开为 01 背包（AC 版）

#include <cstdio>
#include <cstring>
#define MAX 55
int dp[MAX];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k; scanf("%d%d", &n, &k);
        memset(dp, 0, sizeof(int)*(n+10));
        dp[0] = 1;
        for (int i = 0; i < k; ++i) {
            int a, b; scanf("%d%d", &a, &b);
            for (int j = n; j >= a; --j)
                for (int x = 1; x <= b; ++x)
                    if (j >= x*a) dp[j] += dp[j - x*a];
        }
        printf("%d\n", dp[n]);
    }
    return 0;
}

2. 标准多重背包模板（WA 版）

void zeroOnePack(int v, int V) { for(int i=V;i>=v;--i) dp[i]+=dp[i-v]; }
void completePack(int v, int V) { for(int i=v;i<=V;++i) dp[i]+=dp[i-v]; }
void multiplePack(int v, int cnt, int V) {
    if (cnt * v > V) completePack(v, V);
    else {
        int k = 1;
        while (k <= cnt) { zeroOnePack(k*v, V); k <<= 1; }
        if (cnt > 0) zeroOnePack(cnt*v, V); // 剩余部分
    }
}

错误原因：二进制拆分逻辑有误，且组合数计数与最值问题不同，不能直接套用二进制优化（会重复计数）。

3. 正确的多重背包计数优化

对于计数问题，二进制拆分不适用（顺序敏感）。正确做法：

• 单调队列优化（O(nk)）
• 或直接三重循环（数据小 n≤40 完全够用）

关键点总结

1. 组合数 vs 最值：计数问题不可用二进制拆分优化
2. 循环顺序：外层物品，中层容量倒序，内层件数
3. 数据范围小：n≤40，三重循环 40×8×10=3200 次操作，极快

扩展：生成函数视角

每类课程贡献多项式 (1 + x^a + x^{2a} + ... + x^{b·a})，求乘积中 x^n 系数。DP 本质即多项式乘法。