AcWing 11. 背包问题求方案数(java)
原题链接
中等
作者:
CYHMMZDAN
,
2022-12-08 21:16:45
,
所有人可见
,
阅读 149
算法2
java 代码
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
Scanner sc=new Scanner(System.in);
//sc.hasNext();判断扫描器中当前扫描位置后是否还存在下一段,记得(后面要用sc.输入,还有输出)。
n=Scanf_Int();
m=Scanf_Int();
for (int i=1;i<=m;i++){
f[i]=1;
}
for (int i=1;i<=n;i++){
l=Scanf_Int();
r=Scanf_Int();
for (int j=m;j>=l;j--){
m1=dp[j-l]+r;
if (m1>dp[j]){
dp[j]=m1;
f[j]=f[j-l];
}
else if (m1==dp[j]){
f[j]=(f[j]+f[j-l])%(((int) 1e+9)+7);
}
}
}
out.println(f[m]);
out.close();