考察点

本质上还是01背包

Code

#include <iostream>

using namespace std;

const int N=110;

int v[N][N],w[N][N];
int s[N];
int f[N][N];  // f[i][j]：从前i组里面挑选，体积不超过j 的最大价值
/*
i 不选：f[i][j]=f[i-1][j];
i 选择：f[i][j]=f[i-1][j-v[i][k]]+w[i][k], k：选择i组第k个物品
*/
int n,m;

int main(){
    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=0;j<=m;j++){
        f[i][j]=f[i-1][j];
        for(int k=0;k<s[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]<<endl;

    return 0;
}