借此机会，整理一下背包中的某几类问题：
物品分组，每组至少选一个：
这个时候
写法1：看别人博客，这样写省去了某些麻烦问题
达不到的dp值为-INF
dp[i][j]=max(dp[i][j],max(dp[i][j-w[x]]+p[x],dp[i-1][j-w[x]]+p[x]));
也可设为-1
在状态转移时判断哪些状态是达不到的。
写法2:
if(dp[i][j-c[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i][j-c[k]]+w[k]); if(dp[i-1][j-c[k]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-c[k]]+w[k]);
这个时候必须注意两次转移的顺序，如果物品的消耗体积可以为0，两次转移的顺序必须严格按照上面，先用该组已有物品被选的状态转移，再用该组没有物品被选的状态转移。
初始化：每到一组，先赋值为 不可达，因为刚才始任何物品都没有选。
特点：必须用二维数组表示
物品分组，每一组至多选一个：
可以用二维表示，也可以用一维表示，
二维表示：
dp[i][j]=max(dp[i][j],dp[i-1][j-w[x]]+p[x]);
初始化：通过上一组赋值即可，因为至多选一个，初始化时是一个都没选时的情形。
for(j=0;j<=sum;j++) //当前组初始化
dp[i][j]=dp[i-1][j];
int ret=dp2[v];
if(cost[ind]) dp2[v]=max( dp2[v] , dp2[v-cost[ind]]+val[ind] );//
else dp2[v]=max(dp2[v],ret+val[ind]);
一维表示必须对体积为0的物体单独处理,二维表示则自然省去了这些麻烦。
初始化：递推之前初始化。
普通01背包
可以用二维，可以用一维。
二维必须要通过拷贝上一组来初始化:
for(j=0;j<=sum;j++) //当前组初始化 dp[i][j]=dp[i-1][j];
dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+p[x]);
一维在递推之前初始化：
此题不必对物品进行排序，虽然我排了
/**==========================================
* This is a solution for ACM/ICPC problem
*
* @source: hdu 3585 AreYouBusy
* @type: 混合背包，要求对背包有深入理解
* @author: wust_ysk
* @blog: http://blog.csdn.net/yskyskyer123
* @email: 2530094312@qq.com
*===========================================*/
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int maxn=100 ;
const int maxV=100 ;
int n,V;
int cost[10000+10];
int val[10000+10];
int dp[maxn+4][maxV+4];
int dp2[maxn+4];
int things;
int st0,st1,st2;
struct A
{
int m,kind;
vector<int >ve;
bool operator<(const A y)const
{
return kind<y.kind;
}
}a[maxn+5];
void check()
{
st0=st1=st2=-1;
int i;
for( i=1;i<=n;i++)
{
if(a[i].kind==0&& st0==-1) st0=i;
else if(a[i].kind==1&& st1==-1) st1=i;
else if(a[i].kind==2&& st2==-1) st2=i;
}
memset(dp[0],-1, (V+1)*sizeof dp[0][1]);
dp[0][0]=0;
memset(dp2,-1,(V+1)*sizeof dp2[0]);
// dp2[0]=0;
}
void atleastone()
{
int st=st0;
if(st==-1) { dp2[0]=0; return;}//
int ed= ~st1 ?st1-1:st2-1;
if(st1==-1&&st2==-1) ed=n;//
for(int i=st;i<=ed;i++)
{
memset(dp[i],-1,(V+1)*sizeof dp[i][0]);
// memcpy(dp[i],dp[i-1],sizeof dp[i-1]);
vector<int > & vet=a[i].ve;
for(int j=0;j<vet.size();j++)
{
int ind=vet[j];
for(int v=V;v>=cost[ind];v--)
{
if( ~dp[i][v-cost[ind] ] ) dp[i][v]=max(dp[i][v],dp[i][v-cost[ind] ]+val[ind]);
if(~dp[i-1][v-cost[ind] ] ) dp[i][v]=max(dp[i][v],dp[i-1][v-cost[ind] ]+val[ind]);
}
}
}
for(int v=0;v<=V;v++)
{
dp2[v]=dp[ed][v];
}
}
void mostone()
{
int st=st1;
if(st==-1) return;
int ed=st2-1;
if(st2==-1) ed=n;
for(int i=st;i<=ed;i++)
{
vector<int > & vet=a[i].ve;
for(int v=V;v>=0;v--)
{
int ret=dp2[v];
for(int j=0;j<vet.size();j++)
{
int ind=vet[j];
if( v-cost[ind]<0||dp2[v-cost[ind]]==-1 ) continue;//
if(cost[ind]) dp2[v]=max( dp2[v] , dp2[v-cost[ind]]+val[ind] );//
else dp2[v]=max(dp2[v],ret+val[ind]);
}
}
}
}
void zeroone()
{
int st=st2;
if(st==-1) return;
int ed=n;
for(int i=st;i<=ed;i++)
{
vector<int > & vet=a[i].ve;
for(int j=0;j<vet.size();j++)
{
int ind=vet[j];
for(int v=V;v>=cost[ind];v--) if( ~dp2[v-cost[ind] ] )
{
dp2[v]=max(dp2[v],dp2[v-cost[ind] ]+val[ind]);
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&V))
{
things=0;
int tot=0;
for(int i=1;i<=n;i++)
{
int mini=INF;
scanf("%d%d",&a[i].m,&a[i].kind);
a[i].ve.clear();
for(int j=1;j<=a[i].m;j++)
{
scanf("%d%d",&cost[things],&val[things]);
a[i].ve.push_back(things);
if(!a[i].kind) mini=min(mini,cost[things]);
things++;
}
if(!a[i].kind) tot+=mini;
}
if(V<tot) {puts("-1");continue; }
if(!n) {puts("0");continue; }
sort(a+1,a+1+n);
check();
atleastone();
mostone();
zeroone();
int maxi=0;
for(int v=0;v<=V;v++)
{
maxi=max(dp2[v] ,maxi );
}
printf("%d\n",maxi);
}
return 0;
}