背包问题求方案数

原题链接

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

using namespace std;

const int N=1010;
const int MOD=1e9+7;

int dp[N],g[N];
int n,v;

int main()
{
    cin>>n>>v;
    dp[0]=0;
    g[0]=1;
    
    for(int i=0;i<n;i++)
    {
        int vi,wi;
        cin>>vi>>wi;
        for(int j=v;j>=vi;j--)
        {
            int cnt=0;
            int ans=max(dp[j],dp[j-vi]+wi);
            if(dp[j]==ans)  cnt+=g[j];
            if(dp[j-vi]+wi==ans)    cnt+=g[j-vi];
            g[j]=cnt%MOD;
            dp[j]=ans;
        }
    }
    
    int ans=0;
    for(int i=0;i<=v;i++)
    {
        ans=max(ans,dp[i]);
    }
    int cnt=0;
    for(int i=0;i<=v;i++)
    {
        if(dp[i]==ans)
            cnt=(cnt+g[i])%MOD;
    }
    printf("%d\n",cnt);
    return 0;
}