Number of solutions for knapsack problem

thought

Same as the shortest circuit , because dp The topology is the shortest path

In the shortest circuit , If there are two points with the same distance to the end , Then the sum of the two schemes is the answer

Recall the state transition equation

The state here is , No more than j The greatest value of time

#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;
}