分组背包
可以看做多重背包的问题的变形,在多重背包问题中,每种物品有s件,那么每种物品就有s+1个子集
在分组背包问题中,每个分组也可以看做是一个,分组中的每件物品看做是一个子集
#include<iostream>
using namespace std;
const int N =110;
int v[N],w[N];
int dp[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int t;
cin>>t;//当前组内有t个
for(int j=1;j<=t;j++){
cin>>v[j]>>w[j];
}
for(int j=m;j>=0;j--){
for(int k=0;k<=t;k++){
if(j>=v[k]){
dp[j]=max(dp[j],dp[j-v[k]]+w[k]);
}
}
}
}
cout<<dp[m];
return 0;
}