做题感悟： 背包问题分着还好解决，如果和起来就是一个很吓人的题。
解题思路： 有三种状态 1 ) 每组至少选择一个 2 ) 每组最多选择一个（分组背包） 3 ) 每组可以选多个（01背包）
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define lld __int64
const double PI = 3.1415926 ;
const double esp = 1e-4 ;
const int md= 2810778 ;
const int INF = 999999999 ;
const int MX = 105 ;
int n,m ;
int dp[MX][MX] ;
void searchA(int nx,int k) // 至少选择一个
{
int v,w ;
for(int i=0 ;i<nx ;i++)
{
scanf("%d%d",&v,&w) ;
for(int j=m ;j>=v ;j--)
{
if(dp[k][j-v]!=-1) // 两个 if 位置不能换
dp[k][j]=max(dp[k][j],dp[k][j-v]+w) ;
if(dp[k-1][j-v]!=-1)
dp[k][j]=max(dp[k][j],dp[k-1][j-v]+w) ;
}
}
}
void searchB(int nx,int k) // 最多选择一个 相当于分组背包
{
int v,w ;
for(int i=0 ;i<=m ;i++)
dp[k][i]=dp[k-1][i] ;
for(int j=0 ;j<nx ;j++)
{
scanf("%d%d",&v,&w) ;
for(int i=m ;i>=v ;i--) // 每次都是从上一个状态转移到当前组的状态
if(dp[k-1][i-v]!=-1)
dp[k][i]=max(dp[k][i],dp[k-1][i-v]+w) ;
}
}
void searchC(int nx,int k) // 随便选 相当于 01 背包
{
int v,w ;
for(int i=0 ;i<=m ;i++) // 必须放在这里，如果放在里面最优值会被替换
dp[k][i]=dp[k-1][i] ;
for(int i=0 ;i<nx ;i++)
{
scanf("%d%d",&v,&w) ;
for(int j=m ;j>=v ;j--)
if(dp[k][j-v]!=-1)
dp[k][j]=max(dp[k][j],dp[k][j-v]+w) ;
}
}
void init() // 初始化
{
for(int i=1 ;i<=n ;i++)
for(int j=0 ;j<=m ;j++)
dp[i][j]=-1 ;
for(int i=0 ;i<=m ;i++)
dp[0][i]=0 ;
}
int main()
{
int nx,cs ;
while(~scanf("%d%d",&n,&m))
{
init() ;
for(int i=1 ;i<=n ;i++)
{
scanf("%d%d",&nx,&cs) ;
if(!cs) // 至少选一个
searchA(nx,i) ;
else if(cs==1) // 最多选一个
searchB(nx,i) ;
else if(cs==2) // 随便选
searchC(nx,i) ;
}
printf("%d\n",dp[n][m]) ;
}
return 0 ;
}