AcWing 9. 分组背包问题
原题链接
中等
作者:
Value
,
2020-05-29 15:55:33
,
所有人可见
,
阅读 480
#include <iostream>
using namespace std;
const int N = 110;
int weight[N][N], value[N][N], s[N];
int f[N];
int main(){
int n, bag;
cin >> n >> bag;
for(int i = 1; i <= n; i ++ ){
cin >> s[i];
for(int j = 0; j < s[i]; j ++ ){
cin >> weight[i][j] >> value[i][j];
}
}
for(int i = 1; i <= n; i ++ ){
for(int j = bag; j >= 1; j -- ){
for(int k = 0; k < s[i]; k ++ ){
if(weight[i][k] <= j) f[j] = max(f[j], f[j - weight[i][k]] + value[i][k]);
}
}
}
cout << f[bag] << endl;
return 0;
}