题意：T时间内做一些任务，每个任务花费一些时间，获取一些快乐值，让快乐值最大。任务分成多组，每组三种情况之一：1.至少选一个 2.至多选一个 3.任意选
两天敲了两遍，很经典的题，得好好搞清背包才好做
代码：
#include#include #include #include #define inf (1<<28)#define nMAX 110int dp[2][nMAX],w[nMAX],p[nMAX];//滚动数组int max(int a,int b){ return a>b?a:b;}int main(){ int n,m,kind,size,i,j,k; int pre,cur; while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d%d",&kind,&size); for(k=1;k<=kind;k++) scanf("%d%d",&w[k],&p[k]); pre=(i+1)%2; cur=i%2; //至少选一个 if(size==0) { for(j=0;j<=m;j++) dp[cur][j]=-inf; for(k=1;k<=kind;k++)//这个是有顺序的 //for(j=w[k];j<=m;j++)//正序 for(j=m;j>=w[k];j--)//逆序，搞错了 { dp[cur][j]=max(dp[cur][j],max(dp[pre][j-w[k]]+p[k],dp[cur][j-w[k]]+p[k])); } } //至多选一个 else if(size==1) { for(j=0;j<=m;j++) dp[cur][j]=dp[pre][j]; for(k=1;k<=kind;k++) //因为dp多了一维，两个for，和j的顺序都不重要了 for(j=w[k];j<=m;j++) { dp[cur][j]=max(dp[cur][j],dp[pre][j-w[k]]+p[k]); } } //任意选 每个组就是一个01背包 else if(size==2) { for(j=0;j<=m;j++) dp[cur][j]=dp[pre][j]; for(k=1;k<=kind;k++) for(j=m;j>=w[k];j--) dp[cur][j]=max(dp[cur][j],dp[cur][j-w[k]]+p[k]); } } n=n%2; dp[n][m]=max(dp[n][m],-1); printf("%d\n",dp[n][m]); } return 0;}