AcWing 9. 分组背包问题
原题链接
中等
作者:
阿飞被注册了
,
2021-06-06 18:23:53
,
所有人可见
,
阅读 260
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 110;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
int n, m;
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];
}