AcWing 9. 分组背包问题
原题链接
中等
C++ 代码
#include <iostream>
using namespace std;
const int N = 110;
int w[N][N],v[N][N],s[N]; // w[i][j]第i组第j个物品的价值,s[i]表示第i组的物品个数
int f[N];
int n, V;
int main() {
cin >> n >> V;
for(int i = 0; i < n; i ++) {
cin >> s[i];
for(int j = 0; j < s[i]; j ++) {
cin >> v[i][j] >> w[i][j];
}
}
for(int i = 0; i < n; i ++) {
for(int j = V; j >= 0; j --) {
for(int k = 0; k < s[i]; k ++) {
if(j - v[i][k] >= 0) {
f[j] = max(f[j], f[j-v[i][k]] + w[i][k]);
}
}
}
}
cout << f[V] << endl;
return 0;
}