点击查看代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int f[N], g[N];
int main()
{
cin >> n >> m;
memset(f, -0x3f, sizeof f);
f[0] = 0;
g[0] = 1;
for (int i = 1; i <= n; i ++) {
int v, w;
cin >> v >> w;
for (int j = m; j >= v; j --) {
int maxv = max(f[j], f[j - v] + w);
int cnt = 0;
if (maxv == f[j]) cnt += g[j];
if (maxv == f[j - v] + w) cnt += g[j - v];
g[j] = cnt % mod;
f[j] = maxv;
}
}
int res = 0, ans = 0;
for (int i = 0; i <= m; i ++) res = max(res, f[i]);
for (int i = 0; i <= m; i ++)
if (f[i] == res)
ans = (ans + g[i]) % mod;
cout << ans << endl;
return 0;
}
- 状态表示
/(f[i][j]/) 表示从前 /(i/) 个物品中选，且体积恰好等于 /(j/) 的选法的最大值
/(g[i][j]/) 表示从前 /(i/) 个物品中选，且体积恰好等于 /(j/) 的情况下取最大值的方案数 - 状态计算
/(f[i][j] = max(f[i – 1][j], f[i – 1][j – v[i]] + w[i])/)
如果 /(f[i – 1][j] > f[i – 1][j – v[i]] + w/)，/(g[i][j] = g[i – 1][j]/)
如果 /(f[i – 1][j] < f[i – 1][j – v[i]] + w/)，/(g[i][j] = g[i – 1][j – v[i]]/)
如果 /(f[i – 1][j] = f[i – 1][j – v[i]] + w/)，/(g[i][j] = g[i – 1][j] + g[i – 1][j – v[i]]/)
原创文章，作者：bd101bd101，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/269312.html