分组背包问题
思路
1.先把每组看成一个整体,把这个整体当成01背包问题来处理
2.在整体选择下每组的物体进行一个循环,选择每组的一个最优的结果
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e2+10;
int f[N],n,m;
typedef pair<int, int> PII;
vector<PII> v[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
for(int j=1;j<=k;j++)
{
int x,y;
cin>>x>>y;
v[i].push_back({x,y});
}
}
for(int i=1;i<=n;i++)
for(int k=m;k>=1;k--)
for(int j=0;j<v[i].size();j++)//如果这两层循环的位置反了那么你做这题就相当于做一个01背包问题了!所以切记不能反
if(k>=v[i][j].first)
f[k]=max(f[k],f[k-v[i][j].first]+v[i][j].second);
cout<<f[m]<<endl;
return 0;
}