python/TangDou/AcWing/BeiBao/11_ErWei_2.cpp

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int f[N][N], g[N][N]; // f[j]、g[j]分别表示体积恰好为j时的最大价值、方案数
int res;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // f[0][0],g[0][0]
    // 在前0个物品中选择，空间恰好是0，最大值f[0][0]=0,g[0][0]=1;
    f[0][0] = 0, g[0][0] = 1;

    // f[0][1~m],g[0][1~m]
    //　在前0个物品中选择，空间恰好是1~m，这是胡说，是不可能的，最大值是f[0][i]=-INF,g[0][i]=0
    for (int i = 1; i <= m; i++) f[0][i] = -INF, g[0][i] = 0;

    for (int i = 1; i <= n; i++) {
        int v, w;
        scanf("%d %d", &v, &w);
        for (int j = 0; j <= m; j++) {
            int val = f[i - 1][j];
            if (j >= v) {
                if (val > f[i - 1][j - v] + w) {
                    f[i][j] = val;
                    g[i][j] = g[i - 1][j];
                } else if (val == f[i - 1][j - v] + w) {
                    f[i][j] = val;
                    g[i][j] = (g[i - 1][j] + g[i - 1][j - v]) % MOD;
                } else {
                    f[i][j] = f[i - 1][j - v] + w;
                    g[i][j] = g[i - 1][j - v];
                }
            } else {
                f[i][j] = val;
                g[i][j] = g[i - 1][j];
            }
        }
    }
    //由于定义的状态表示是“空间恰好是i”，那么最大值的产生，可不一定存储在“空间恰好是m”的状态下，m及以下的各个状态，都可能装着最大值，
    //我们遍历一次f数组，找出最大值，然后二次遍历f数组、g数组,累加可以获得最大值时的方案数量。
    int mx = 0;
    for (int i = 0; i <= m; i++) mx = max(mx, f[n][i]);

    for (int i = 0; i <= m; i++)
        if (f[n][i] == mx) res = (res + g[n][i]) % MOD;

    printf("%d\n", res);
    return 0;
}