hdu 3535 涵盖了分组背包的各种情况 非常好的背包题目
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1394 Accepted Submission(s): 529
/*
题意 xiaoA想尽量多花时间做ACM，但老板要求他在t时间内做完n堆工作，每个工作耗时cost，
得到幸福感val，每个工作有num[i]个工作，每堆工作都有一个性质，0表示至少要做里面的1个工作，
1表示最多做里面的1个工作，2表示随意，做或不做都行。最后问在符合老板要求的情况下的最大幸福感，
怎么都不符合要求就输出-1.
题意是有n组背包，每组有一个属性:0表示该组内必须取一个，1表示该组内最多取一个，
2表示该组内可以任意取。每组背包内有一些物品，有一定的价值和花费值。最后给定花费求最大价值。
思路：
数组dp[i][j],表示第i组，时间剩余为j时的快乐值。每得到一组工作就进行一次DP，所以dp[i]为第i组的结果
第一类
至少选一项，即必须要选，那么在开始时，对于这一组的dp的初值，应该全部赋为负无穷，
这样才能保证不会出现都不选的情况。状态转移方程为dp[i][k]=max{ dp[i][k],dp[i-1][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }。
dp[i][k]是不选择当前工作；dp[i-1][k-cost[j]]+val[k]是选择当前工作，但是是第一次在本组中选，
由于开始将该组dp赋为了负无穷，所以第一次取时，必须由上一组的结果推知，这样才能保证得到全局最优解；
dp[i][k-cost[j]]+val[j]表示选择当前工作，并且不是第一次取。
第二类
最多选一项，即要么不选，一旦选，只能是第一次选。
所以状态转移方程为dp[i][k]=max{ dp[i][k],dp[i-1][k-cost[j]]+val[k]}。
由于要保证得到全局最优解，所以在该组DP开始以前，应该将上一组的DP结果先复制到这一组的dp[i]数组里，
因为这一组的数据是在上一组数据的基础上进行更新的。
第三类
任意选，即不论选不选，选几次都可以，
显然状态转移方程为dp[i][k]=max{ dp[i][k],dp[i-1][k-cost[j]]+val[k],dp[i][k-cost[j]]+val[j] }
。同样要保证为得到全局最优解，先复制上一组解。
以上为参考作者 ‘ 等待电子的砹 ’ 的文章
*/
#include<stdio.h>
#include<string.h>
#include<limits.h>
int n,t;
int dp[110][110],cost[110],val[110];
int mmax(int x,int y)
{
if(x>y) return x;
else return y;
}
int main()
{
int i,j,flag,m,k,ans;
while(scanf("%d %d",&n,&t)!=EOF)
{
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
{
scanf("%d %d",&m,&flag);//m是每组的个数
for(j=1;j<=m;j++)
{
scanf("%d %d",&cost[j],&val[j]);
}
if(flag==0)//当前组至少拿一个
{
for(j=0;j<=t;j++)
dp[i][j]=-1000000;//INT_MIN;//为了保证至少拿一个
for(j=1;j<=m;j++)
for(k=t;k>=cost[j];k--)
{
dp[i][k]=mmax(dp[i][k],dp[i][k-cost[j]]+val[j]);//这句话与下面那句话不能交换位置 不知道为什么
dp[i][k]=mmax(dp[i][k],dp[i-1][k-cost[j]]+val[j]);
}
}
else if(flag==1)//当前组最多拿一个
{
for(j=0;j<=t;j++)
dp[i][j]=dp[i-1][j];
for(j=1;j<=m;j++)
for(k=t;k>=cost[j];k--)
{
dp[i][k]=mmax(dp[i][k],dp[i-1][k-cost[j]]+val[j]);
}
}
else //当前组随便拿多少个
{
for(j=0;j<=t;j++)
dp[i][j]=dp[i-1][j];
for(j=1;j<=m;j++)
for(k=t;k>=cost[j];k--)
{
dp[i][k]=mmax(dp[i][k],dp[i][k-cost[j]]+val[j]);
dp[i][k]=mmax(dp[i][k],dp[i-1][k-cost[j]]+val[j]);
}
}
}
ans=mmax(dp[n][t],-1);
printf("%d\n",ans);
// printf("%d\n",dp[n][t]);
}
return 0;
}
