概览
有N组物品和一个容量为V的背包
每组物品有若干,同组内的物品只能选一个
分组背包问题是枚举每组选哪个或者不选, 完全背包问题是枚举某个物品选几个或者不选
题解
状态表示
- 集合: 只从前i组物品中选,且总体积不大于j的所有做法
- 属性: Max
状态计算
f[i,j]
集合划分,对第i个组怎么操作?
对于第i组,不选,选第1个物品,选第2个物品,…, 选第k个物品
f[i-1,j] , f[i-1, j-v[i,k]] + w[i,k] k
用的是上层状态则从大到小枚举,用的是本层状态则从小到大枚举
代码
// 当没有思路时,回到最初的步骤去思考应该如何做
// f[i,j] 只从前i组物品中选,且总体积不大于j的所有选法的最大值
// f[i,j] 最多选一个,那么可以不选,选a, 选b, 选c, 等等
// f[i,j] = max(f[i-1,j], f[i-1,j-v[k]]+w[k]) 上层从大到小枚举
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> s[i];
for (int j = 0; j < s[i]; j ++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i ++)
for (int j = m; j >= 0; j --)
for (int k = 0; k < s[i]; k ++)
if (j >= v[i][k]) // 务必使其有意义
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}