背包问题的模板,以后可以背下来套用噢。
但是更多的时候要像 传送门 一样有转换的过程
#include<bits/stdc++.h> using namespace std; const int N=110; int n,m,s[N],v[N][N],w[N][N],f[N]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&s[i]); for(int j=1;j<=s[i];j++) scanf("%d%d",&v[i][j],&w[i][j]); } f[0]=0; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=s[i];k++) if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); printf("%d\n",f[m]); return 0; }