AcWing 11. 背包问题求方案数
原题链接
中等
作者:
fancywing
,
2021-01-19 11:19:55
,
所有人可见
,
阅读 374
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int N = 1010;
int v[N],w[N],f[N],cnt[N];
int main(){
int n,m;
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>v[i]>>w[i];
for(int i = 0; i <= m; i++) cnt[i] = 1;
for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
int val = f[j-v[i]]+w[i];
if(val > f[j]){ // 选了i物品,大于之前的了
f[j] = val;
cnt[j] = cnt[j-v[i]];
}else if(val == f[j]){
cnt[j] = (cnt[j]+ cnt[j-v[i]])%mod;
}
}
}
cout<< cnt[m] <<endl;
return 0;
}