AcWing 11. 背包问题求方案数

//g[i,j]表示f[i,j]取最大值的方案数目

//体积最多是j 全部为0，v>=0

//体积恰好为j f[0][0]=0,f[i]=无穷，v>=0

//体积至少是j f[0][0]=0,f[i]=无穷，体积为负数时于0取大

#include <cstring>

#include <iostream>

using namespace std;

const int N = , mod = 1e9 + ;

int n, m;

int f[N], g[N];

int main() {

    cin >> n >> m;

    memset(f, -0x3f, sizeof f);//恰好，所以负无穷

    f[] = ;

    g[] = ;

    for (int i = ; i < n; i ++ ) {

        int v, w;

        cin >> v >> w;

        for (int j = m; j >= v; j -- ) {

            int maxv = max(f[j], f[j - v] + w);//先求最大值

            int cnt = ;

            if (f[j] == maxv) cnt += g[j];//记录方案数目

            if (f[j - v] + w == maxv) cnt += g[j-v];

            g[j] = cnt % mod;

            f[j] =  maxv;

        }

    }

    int res = ;//求最大价值

    for (int i = ; i <= m; i ++ ) res = max(res , f[i]);

    int cnt = ;//求最大价值时的方案数目

    for (int i = ; i <= m; i ++ )

        if (f[i] == res)

            cnt = (cnt + g[i]) % mod;

    cout << cnt << endl;

    return ;

}