题解 | 【模板】01背包（计数）

#include <bits/stdc++.h>
using namespace std;

struct it {
    int v = 0;
    int w = 0;
};
const int N = 1e4 + 5;
const int M = 1e9 + 7;
it a[N];
int f[N];  
int cnt[N];

int main() {
    int T;
    cin >> T;
    while (T--) {  // 处理多组测试数据
        int n, m;
        cin >> n >> m;  // n：物品数量，m：背包最大容量
        for (int i = 1; i <= n; i++) {
            cin >> a[i].w >> a[i].v;  // 输入每个物品的体积(w)和价值(v)
        }
        // 初始化：重置f和cnt数组，避免上一组数据残留影响当前组计算
        memset(f,0,sizeof f);   // f数组置0：初始无物品，任意体积的最大价值为0
        memset(cnt,0,sizeof cnt);// cnt数组置0：初始无合法方案（除体积0外）
        cnt[0] = 1;  // 体积0、价值0的方案数为1（不选任何物品，唯一初始方案）

        // 逆序遍历物品（保持原逻辑，等价于正序遍历物品，对应考虑第i到n个物品的状态）
        for (int i = n; i >= 1; i--) {
            // 逆序遍历体积（01背包一维优化核心！避免同一物品被重复选取）
            // 保证更新f[j]时，f[j-a[i].w]是未选当前物品的上一轮状态
            for (int j = m; j >= a[i].w;j--) {  
                // 情况1：选当前物品后的价值 = 体积j当前的最大价值 → 累加方案数
                if (f[j] == f[j - a[i].w] + a[i].v) {
                    cnt[j] = (cnt[j] + cnt[j - a[i].w]) % M;  // 方案数累加，取模防溢出
                } 
                // 情况2：选当前物品后的价值 > 体积j当前的最大价值 → 更新最大价值并重置方案数
                else if (f[j] < f[j - a[i].w] + a[i].v) {
                    f[j] = f[j - a[i].w]+a[i].v;  // 更新体积j的最大价值
                    cnt[j] = cnt[j - a[i].w] % M;  // 重置为选当前物品对应的方案数
                }
                // 情况3：选当前物品后的价值 < 现有最大价值 → 不做任何操作，保持原状态
            }

        }

        // 统计全局最大价值对应的总方案数
        int tmp = *max_element(f, f + m + 1);  // 找到0~m体积范围内的最大价值
        int res = 0;
        for (int j = 0; j <= m; j++) {
            if (f[j] == tmp) {  // 累加所有达到最大价值的体积对应的方案数
                res = (res + cnt[j]) % M;
            }
        }
        cout << res << endl;
    }

    return 0;
}