分组背包问题
状态表示:
集合:f[i][j]
:考虑前 i 组物品,且总体积不超过 j 的所有方案
属性:Max
状态计算:
1、第 i 组物品一个不选
f[i][j] = f[i - 1][j];
2、第 i 组物品中选第 k 个物品
for (int k = 1; k <= s[i]; k++) // s[i] 为第 i 组物品的个数
f[i][j] = min(f[i - 1][j - v[i][k]] + w[i][k]);
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, m;
int s[N];
int v[N][N], w[N][N];
int f[2][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
for (int j = 1; j <= s[i]; j++) scanf("%d%d", &v[i][j], &w[i][j]);
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) {
f[i & 1][j] = f[i - 1 & 1][j];
for (int k = 1; k <= s[i]; k++)
if (j >= v[i][k]) f[i & 1][j] = max(f[i & 1][j], f[i - 1 & 1][j - v[i][k]] + w[i][k]);
}
printf("%d", f[n & 1][m]);
return 0;
}