DP可行性问题，可以把多重背包转化为完全背包来做
#include <bits/stdc++.h> using namespace std; typedef long long ll; //typedef __int128 LL; //typedef unsigned long long ull; //#define F first //#define S second typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<ld,ld> pdd; const ld PI=acos(-1); const ld eps=1e-9; //unordered_map<int,int>mp; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back const int seed=131; const int M = 107; int v[M][M],w[M][M]; int nm[M]; int f[M]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,V; cin>>n>>V; for(int i=1;i<=n;i++) { cin>>nm[i]; for(int j=1;j<=nm[i];j++) cin>>v[i][j]>>w[i][j]; } //f[1&1][] // int g=1; for(int i=1;i<=n;i++) { for(int j=V;j>=1;j--) for(int k=1;k<=nm[i];k++) { if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); } } cout<<f[V]<<endl; return 0; }
