AcWing 11. 背包问题求方案数
原题链接
中等
作者:
再摆紫砂
,
2022-11-01 01:59:56
,
所有人可见
,
阅读 295
对于每个状态f[i][j]都是由f[i - 1][j](不选第i个物品)和f[i - 1][j - v[i]] + w[i](选第i个物品转移过来的),根据这一点可以用g[i][j]来存储每个状态的方案数
方案数g[i][j]转移方程
如果是由f[i - 1][j]转移过来则g[i][j] = g[i][j] + g[i - 1][j];
如果是由f[i - 1][j - v[i]] + w[i]转移过来则g[i][j] = g[i][j] + g[i - 1][j - v[i]]
二维代码
/*
g[i][j]取最大值的方案数
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int v[N], w[N];
int f[N][N];
int g[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) {
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
g[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
if (f[i][j] == f[i - 1][j]) {
g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
}
if (j >= v[i] && f[i][j] == f[i - 1][j - v[i]] + w[i]) {
g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mod;
}
}
}
int res = 0;
for (int i = 0; i <= m; i++) {
if (f[n][i] == f[n][m]) {
res = (res + g[n][i]) % mod;
}
}
cout << res << '\n';
return 0;
}
一维优化
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int f[N], g[N];
int main() {
cin >> n >> m;
//体积恰好是j
memset(f, -0x3f, sizeof f);
f[0] = 0;
g[0] = 1;
for (int i = 0; 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;//记录最大值时的总价值
for (int i = 0; i <= m; i++) res = max(res, f[i]);
int cnt = 0;
for (int i = 0; i <= m; i++) {
if (res == f[i]) {//如果等于最大值
cnt = (cnt + g[i]) % mod;
}
}
cout << cnt << '\n';
return 0;
}