闫式dp分析法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N] , cnt[N];
int mod = 1e9 + 7;
int n , m ;
int main() {
    cin >> n >> m;

    for (int i = 0 ; i <= m ; i ++ ) cnt[i] = 1; // 表示每一个物品初始时都可以被选
    for (int i = 1;  i <= n ; i ++ ) {
        int v , w;
        cin >> v >> w;
        for (int j = m ; j >= v ; j -- ) {
            int value = f[j - v] + w;
            if (value > f[j]) {
                f[j] = value;
                cnt[j] = cnt[j - v];
            }
            else if (value == f[j]) cnt[j] = (cnt[j] + cnt[j - v]) % mod;
        }
    }
    cout << cnt[m];



    return 0;
}