/* 题意：n组数据，容积为v，temp为种类，0类至少选一个，1类至多选一个，2自由选择，求最大价值 分组混合背包，分别确定每一组的状态， 种类0和2时，状态转移方程相同，只是初始化不同， */ #include#include #include using namespace std; #define INF -999999 int dp[105][105]; int main() { int n,v; while(scanf("%d%d",&n,&v)!=EOF) { memset(dp,0,sizeof(dp)); int i,j,m,temp; for(i=1;i<=n;i++) { scanf("%d%d",&m,&temp); int cost[105],weight[105]; for(j=1;j<=m;j++) scanf("%d%d",&cost[j],&weight[j]); if(temp==0) { int k; for(j=0;j<=v;j++) dp[i][j]=INF; for(j=1;j<=m;j++) for(k=v;k> =cost[j];k--) dp[i][k]=max(dp[i][k],max(dp[i-1][k-cost[j]],dp[i][k-cost[j]])+weight[j]); } else if(temp==1) { int k; for(j=0;j<=v;j++) dp[i][j]=dp[i-1][j]; for(j=1;j<=m;j++) for(k=cost[j];k<=v;k++) dp[i][k]=max(dp[i][k],dp[i-1][k-cost[j]]+weight[j]); } else //01背包 { int k; for(j=0;j<=v;j++) dp[i][j]=dp[i-1][j]; for(j=1;j<=m;j++) for(k=v;k>=cost[j];k--) dp[i][k]=max(dp[i][k],max(dp[i-1][k-cost[j]],dp[i][k-cost[j]])+weight[j]); } } dp[n][v]=max(dp[n][v],-1); printf("%d\n",dp[n][v]); } return 0; }