01背包+互斥背包+条件背包。详细见代码：
#include<iostream>
using namespace std;
int n,t,m,s;
int cost[105],hap[105];
int f[105];
int main()
{
while(scanf("%d%d",&n,&t)!=EOF)
{
int i,j,k;
memset(f,-1,sizeof(f));
f[0]=0;
for(k=1;k<=n;k++)
{
scanf("%d%d",&m,&s);
for(i=0;i<m;i++)
scanf("%d%d",&cost[i],&hap[i]);
if(s==0)
{
int d[105];
memset(d,-1,sizeof(d));
for(i=0;i<m;i++)
for(j=t;j>=cost[i];j--)
{
if(d[j-cost[i]]!=-1&&d[j]<d[j-cost[i]]+hap[i])
d[j]=d[j-cost[i]]+hap[i];
if(f[j-cost[i]]!=-1&&d[j]<f[j-cost[i]]+hap[i])
d[j]=f[j-cost[i]]+hap[i];
}
memcpy(f,d,sizeof(d));
}
else if(s==1)
{
for(j=t;j>=0;j--)
{
int temp=-1; //注意:找这m个中的最大值时,应先找到最大值,再更新f[j].不要边比较边更新,如果出现f[j]<f[j-cost[i]]+hap[i]而更新f[j],那么当下次出现f[j]<f[j-cost[i]]+hap[i],并且cost[i]==0时,就会变成f[j]+hap[i],但f[j]已经更新,就会出错.
for(i=0;i<m;i++)
{
if(j-cost[i]>=0&&f[j-cost[i]]!=-1&&temp<f[j-cost[i]]+hap[i])
temp=f[j-cost[i]]+hap[i];
}
f[j]=f[j]>temp?f[j]:temp;
}
}
else if(s==2)
{
for(i=0;i<m;i++)
for(j=t;j>=cost[i];j--)
if(f[j-cost[i]]!=-1&&f[j]<f[j-cost[i]]+hap[i])
f[j]=f[j-cost[i]]+hap[i];
}
}
int ans=-1;
for(i=0;i<=t;i++)
if(ans<f[i]) ans=f[i];
printf("%d\n",ans);
}
return 0;
}posted on 2010-08-18 09:58
wuxu 阅读(301)
评论(0) 编辑 收藏 引用 所属分类:
动态规划