1.朴素

#include <iostream>

using namespace std;
const int  N=105;
int n,m;
int f[N][N],v[N][N],w[N][N],s[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        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=0;j<=m;j++){
            f[i][j]=f[i-1][j];//不选   这里要放循环外边，因为是不选这一组，若放里边会出现刷新最大值的情况！！！
            for(int k=1;k<=s[i];k++){
                if(v[i][k]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<f[n][m];
    //cout << "Hello world!" << endl;
    return 0;
}

2.一维优化

#include <iostream>

using namespace std;
const int  N=105;
int n,m;
int f[N][N],v[N][N],w[N][N],s[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        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=0;j<=m;j++){
            f[i][j]=f[i-1][j];//不选   这里要放循环外边，因为是不选这一组，若放里边会出现刷新最大值的情况！！！
            for(int k=1;k<=s[i];k++){
                if(v[i][k]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<f[n][m];
    //cout << "Hello world!" << endl;
    return 0;
}