AcWing 11. 背包问题求方案数
原题链接
中等
作者:
我呼吸了
,
2022-05-14 15:13:30
,
所有人可见
,
阅读 84
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int P = 1e9 + 7;
int f[N][N];
int n, m;
int v[N], w[N];
int cnt[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
cnt[0][0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i-1][j];
cnt[i][j] = cnt[i-1][j];
if(j >= v[i])
{
if(f[i-1][j-v[i]]+w[i] > f[i][j]) cnt[i][j] = cnt[i-1][j-v[i]];
if(f[i-1][j-v[i]]+w[i] == f[i][j]) cnt[i][j] = (cnt[i][j]+cnt[i-1][j-v[i]])%P;
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
}
int res = 0;
for(int j = 0; j <= m; j++)
{
if(f[n][j] == f[n][m]) res = (res + cnt[n][j]) % P;
}
cout << res << endl;
return 0;
}