hdu 3535 背包综合题

 1 /*
 2 有n组背包，每组都有限制
 3 0、至少选一项
 4 1、最多选一项
 5 2、任意选
 6 */
 7 #include <iostream>
 8 #include <cstdio>
 9 #include <cstring>
10 using namespace std;
11 
12 const int maxn=105;
13 const int INF=0xfffffff;
14 int dp[maxn][maxn];//第i组,剩余时间j的最大价值
15 int w[maxn],v[maxn];
16 inline int max(int a,int b){return a>b?a:b;}
17 int main()
18 {
19     int n,t,m,flag,i,j,k;
20     while(~scanf("%d%d",&n,&t))
21     {
22         memset(dp[0],0,sizeof(dp));
23         for(i=1;i<=n;i++)
24         {
25             scanf("%d%d",&m,&flag);
26             for(j=1;j<=m;j++) scanf("%d%d",w+j,v+j);
27             if(flag==0)
28             {
29                 for(j=0;j<=t;j++) dp[i][j]=-INF;
30                 for(j=1;j<=m;j++)
31                     for(k=t;k-w[j]>=0;k--)
32                         dp[i][k]=max(dp[i][k],max(dp[i-1][k-w[j]]+v[j],dp[i][k-w[j]]+v[j]));//这组不选,第一次选,多次选
33             }
34             else if(flag==1)
35             {
36                 for(j=0;j<=t;j++) dp[i][j]=dp[i-1][j];
37                 for(j=1;j<=m;j++)
38                     for(k=t;k-w[j]>=0;k--)
39                         dp[i][k]=max(dp[i][k],dp[i-1][k-w[j]]+v[j]);//这组不选,第一次选
40             }
41             else
42             {
43                 for(j=0;j<=t;j++) dp[i][j]=dp[i-1][j];
44                 for(j=1;j<=m;j++)
45                     for(k=t;k-w[j]>=0;k--)
46                         dp[i][k]=max(dp[i][k],max(dp[i-1][k-w[j]]+v[j],dp[i][k-w[j]]+v[j]));//这组不选,第一次选，多次选
47             }
48         }
49         int ans=max(dp[n][t],-1);
50         printf("%d
",ans);
51     }
52     return 0;
53 }