题目9. 分组背包问题题目描述有N NN组物品和一个容量是V VV的背包。每组物品有若干个同一组内的物品最多只能选一个。每件物品的体积是v i j v_{ij}vij​价值是w i j w_{ij}wij​其中i ii是组号j jj是组内编号。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行有两个整数N NNV VV用空格隔开分别表示物品组数和背包容量。接下来有N NN组数据每组数据第一行有一个整数S i S_iSi​表示第i ii个物品组的物品数量每组数据接下来有S i S_iSi​行每行有两个整数v i j v_{ij}vij​,w i j w_{ij}wij​用空格隔开分别表示第i ii个物品组的第j jj个物品的体积和价值输出格式输出一个整数表示最大价值。数据范围0 N , V ≤ 100 0N,V≤1000N,V≤1000 S i ≤ 100 0S_i≤1000Si​≤1000 v i j , w i j ≤ 100 0v_{ij},w_{ij}≤1000vij​,wij​≤100时空限制1s / 64MB输入样例3 5 2 1 2 2 4 1 3 4 1 4 5输出样例8思路代码1二维数组#includebits/stdc.husingnamespacestd;constintN10010;intn,V,s[N],v[N][N],w[N][N],f[N][N];intmain(){cinnV;for(inti1;in;i){cins[i];for(intj0;js[i];j)cinv[i][j]w[i][j];}for(inti1;in;i)for(intj0;jV;j){f[i][j]f[i-1][j];for(intk0;ks[i];k)if(jv[i][k])f[i][j]max(f[i][j],f[i-1][j-v[i][k]]w[i][k]);}coutf[n][V];return0;}代码2一维数组#includebits/stdc.husingnamespacestd;constintN10010;intn,V,s[N],v[N][N],w[N][N],f[N];intmain(){cinnV;for(inti1;in;i){cins[i];for(intj0;js[i];j)cinv[i][j]w[i][j];}for(inti1;in;i)for(intjV;j0;j--)for(intk0;ks[i];k)if(jv[i][k])f[j]max(f[j],f[j-v[i][k]]w[i][k]);coutf[V];return0;}结果