题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=3535
//不想写题解,这道题让我对背包的理解更深了,我相信我不会忘记的。。。。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int INF=0x3f3f3f3f; int dp[][];
int t[],g[]; int main()
{
int N,T;
while(scanf("%d%d",&N,&T)==)
{
memset(dp,,sizeof(dp));
for(int i=; i<=N; i++)
{
int n,s;
scanf("%d%d",&n,&s);
for(int k=; k<=n; k++)
scanf("%d%d",&t[k],&g[k]);
if(s==) ///至少选一件
{
for(int j=; j<=T; j++)
dp[i][j]=-INF;
for(int j=; j<=n; j++)
for(int k=T; k>=t[j]; k--)
dp[i][k]=max(dp[i][k],max(dp[i][k-t[j]]+g[j],dp[i-][k-t[j]]+g[j]));
}
else if(s==) ///最多选一件
{
for(int j=; j<=T; j++)
dp[i][j]=dp[i-][j];
for(int j=; j<=n; j++)
for(int k=T; k>=t[j]; k--)
dp[i][k]=max(dp[i][k],dp[i-][k-t[j]]+g[j]);
}
else ///随便选
{
for(int j=; j<=T; j++)
dp[i][j]=dp[i-][j];
for(int j=; j<=n; j++)
for(int k=T; k>=t[j]; k--)
dp[i][k]=max(dp[i][k],max(dp[i-][k-t[j]]+g[j],dp[i][k-t[j]]+g[j]));
}
}
if(dp[N][T]<=) dp[N][T]=-;
printf("%d\n",dp[N][T]);
}
return ;
}