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

[模板]01背包（计数）

代表占用体积能达到的最大价值

代表占用体积能达到最大价值时的方案数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll NEG_INF = - (4000000000000000000LL);

void solve(int testcase) {
    ll n, m;
    cin >> n >> m;
    vector<ll> A(m + 1, NEG_INF);
    A[0] = 0;
    vector<ll> B(m + 1, 0);
    B[0] = 1;
  
    for (ll _ = 0; _ < n; _++) {
        ll w, v;
        cin >> w >> v;
        vector<ll> nA(m + 1, NEG_INF);
        vector<ll> nB(m + 1, 0);
      
        for (ll i = m; i >= w; i--) {
            ll prev = i - w;
            if (A[prev] == NEG_INF) continue;
            ll nv = A[prev] + v;
            if (nv > nA[i]) {
                nA[i] = nv;
                nB[i] = B[prev];
            } else if (nv == nA[i]) {
                nB[i] = (nB[i] + B[prev]) % MOD;
            }
        }
      
        for (ll i = 0; i <= m; i++) {
            if (nA[i] > A[i]) {
                A[i] = nA[i];
                B[i] = nB[i];
            } else if (nA[i] == A[i]) {
                B[i] = (B[i] + nB[i]) % MOD;
            }
        }
    }
  
    for (ll i = m; i >= 0; i--) {
        if (A[i] >= 0) {
            cout << B[i] << "\n";
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        solve(t);
    }
    return 0;
}