AcWing
9. 分组背包问题
分组背包问题。定义二维状态数组f[i][j]表示考虑前i组物品，背包容量为j时，所有方案中的最大价值，那么分组背包问题是01背包问题的变种。
类似地，将f[i][j]分为以下若干个集合：
- 背包容量为
j时，选择装下组i中的物品1； - 背包容量为
j时，选择装下组i中的物品2； - ……
- 背包容量为
j时，选择装下组i中的物品k； - ……
- 背包容量为
j时，选择不装下组i中的某种物品；
保证将f[i][j]分为这些集合之后不重不漏。则对于普遍的f[i][j]，其值即为这若干种方案中价值最大的那个。
所以，有：
f[i][j] = max{f[i-1][j], f[i-1][j-v[i][0]]+w[i][0], f[i-1][j-v[i][1]]+w[i][1], ..., f[i-1][j-v[i][k]]+w[i][k], ...}；
使用一层循环来寻找这个最大值。
考虑边界条件，f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, ...，即当不取任何一组物品时，总价值一定为0.
考虑优化空间，使用一维数组，外层循环依次枚举分组，次外层循环必须从大到小枚举背包容量，这样每个分组最多只会取一次，而且每次会由内层循环选出最大价值的组内选项(或不选)，f[j]、f[j-v[i][k]]取得的都是上一组时的值。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 110, M = 110;
int s[N], v[N][N], w[N][N];
int f[M];
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> s[i];
for(int j = 1; j <= s[i]; j++){
cin >> v[i][j] >> w[i][j];
}
}
for(int i = 1; i <= n; i++)
for(int j = m; j >= 1; j--)
for(int k = 1; 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;
}