/* 題意: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; }