算法1

(分组背包) $O(n^3)$

注意：由于每组物品只能选一个，所以转移的时候f[i][j]可以从f[i-1][j-v[i][k]转移过来

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3;

int n,m;
int w[N][N],v[N][N];
int num[N];
int f[110][110];
int res;

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        for(int j=1;j<=num[i];j++) cin>>v[i][j]>>w[i][j];
    }

    for(int i=1;i<=n;i++)//枚举每一组
    for(int j=0;j<=m;j++)//枚举体积
    {
    f[i][j]=f[i-1][j];//不选当前这一组
    for(int k=1;k<=num[i];k++)//枚举每一组中的每个物品
    if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
    }

    cout<<f[n][m];
    return 0;
}