分三种情况。
至少取一种 那可以直接取 或者从上一种情况来取.dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v,dp[i][k-a[j].c]+a[j].v);
至多取一种 只能从上一种情况来取 dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v);
任意取 dp[i][k]=max(dp[i][k],dp[i-1][k-a[j].c]+a[j].v,dp[i][k-a[j].c]+a[j].v);
#include<stdio.h>
#include<string.h>
#define maxn 110
#define INF 99999999
int dp[maxn][maxn];
struct node
{
int v;
int c;
}a[maxn];
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int i,j,n,m,t,s,k;
while(scanf("%d%d",&n,&t)!=EOF)
{
memset(dp,,sizeof(dp));//初始化为0,保证dp[1][0]=0;
for(i=;i<=n;i++)
{
scanf("%d %d",&m,&s); for(j=;j<=m;j++)
scanf("%d%d",&a[j].c,&a[j].v); if(s==)//至少1
{
for(k=;k<=t;k++)//保证下一次选的时候一定选一个
dp[i][k]=-INF; for(j=;j<=m;j++)
{
for(k=t;k>=a[j].c;k--)
{
//下面的顺序不能调换 如果dp[i-1]在前面，有可能就更新了2次，v被加了2次。
//可以考虑一下
//直接选当前的 先更新自己，
dp[i][k]=max(dp[i][k],dp[i][k-a[j].c]+a[j].v);
//从前一种情况来选当前的
dp[i][k]=max(dp[i][k],dp[i-][k-a[j].c]+a[j].v);
}
}
}
else if(s==)//最多选一个 所以从前一种来考虑
{
for(k=;k<=t;k++)
dp[i][k]=dp[i-][k];
for(j=;j<=m;j++)
{
for(k=t;k>=a[j].c;k--)
{
dp[i][k]=max(dp[i][k],dp[i-][k-a[j].c]+a[j].v);
}
}
}
else if(s==)//任意
{
for(k=;k<=t;k++)
dp[i][k]=dp[i-][k];
for(j=;j<=m;j++)
{
for(k=t;k>=a[j].c;k--)
{
dp[i][k]=max(dp[i][k],dp[i][k-a[j].c]+a[j].v);
dp[i][k]=max(dp[i][k],dp[i-][k-a[j].c]+a[j].v);
}
}
}
}
dp[n][t]=max(dp[n][t],-);
printf("%d\n",dp[n][t]);
}
}