背包问题求方案数

思想

与最短路一样，因为dp就是拓扑图跑最短路

最短路中，如果有两个点到终点的距离相同，那么这两个点方案数加在一起就是答案

回忆一下状态转移方程

这里的状态就是，不超过j时的最大价值

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1010, mod = 1e9 + 7;

int n, m;
int f[N], g[N];

int main()
{
    
    cin >> n >> m;
    
    f[0] = 0;
    g[0] = 1;

    for (int i = 0; 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 s = 0;
            if (f[j] == maxv) s = g[j];
            if (f[j - v] + w == maxv) s = (s + g[j - v]) % mod;
            f[j] = maxv, g[j] = s;
        }
    }

    int sum = 0;
    for (int i = 0; i <= m; i ++ )
        if (f[i] == f[m])
            sum = (sum + g[i]) % mod;

    cout << sum << endl;

    return 0;
}