AcWing 11. 背包问题求方案数
原题链接
中等
作者:
wangyj
,
2021-01-17 13:17:47
,
所有人可见
,
阅读 328
#include<cstring>
#include<iostream>
using namespace std;
const int MOD=1e9+7;
int n,m,f[1005],g[1005],i,j,v,w,s,maxv,ans=0,sum=0;
int main()
{
scanf("%d%d",&n,&m);
memset(f,-0x3f,sizeof f);
f[0]=0,g[0]=1;
for(i=0;i<n;i++){
scanf("%d%d",&v,&w);
for(j=m;j>=v;j--){
maxv=max(f[j],f[j-v]+w),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;
}
}
for(i=1;i<=m;i++)if(f[i]>f[ans])ans=i;
for(i=0;i<=m;i++)if(f[i]==f[ans])sum=(sum+g[i])%MOD;
printf("%d\n",sum);
return 0;
}