33 lines
1.0 KiB
C++
33 lines
1.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 110;
|
||
|
||
int n; //n类物品
|
||
int m; //背包上限为m
|
||
int v[N][N]; //体积
|
||
int w[N][N]; //价值
|
||
int s[N]; //每类物品的个数
|
||
int f[N]; //dp数组，最大值
|
||
|
||
//分组背包
|
||
int main() {
|
||
//优化输入
|
||
ios::sync_with_stdio(false);
|
||
cin >> n >> m;
|
||
|
||
for (int i = 1; i <= n; i++) {//枚举每类物品,比如：水果，蔬菜，肉类...
|
||
cin >> s[i]; //此类物品中物品的个数,比如2，可能是苹果、香蕉
|
||
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 >= 0; j--) //遍历每个可能的体积
|
||
for (int k = 1; k <= s[i]; k++)//遍历k个物品
|
||
if (v[i][k] <= j)
|
||
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
|
||
|
||
cout << f[m] << endl;
|
||
return 0;
|
||
} |