背包. 题目来源：
http://acm.hdu.edu.cn/showproblem.php?pid=3236初看题目可以知道这是个背包问题，但物品分为普通和特殊两种，并且要求特殊的全部得到。如果只有这两个限制，可以做两次二维背包，先做特殊物品背包，然后把不满足题目要求的状态删掉(同时可以判断能否满足女友的要求)，再做普通物品背包。但是，题目又多了个特殊情况，就是可以免费赠送一个物品，那么可以通过加维来处理。用f[i][j][s]表示得到的最大happy值，其中i表示第一张购物卷，j表示第二张购物卷，s==0表示未赠送，s==1表示已赠送。
普通物品：f[i][j][s]=max{f[i][j][s],f[i-price[k]][j][s]+hap[k],f[i][j-price[k]][s]+hap[k]} (s=0,1)
另外当s==1时还有一种情况，f[i][j][1]=max{f[i][j][1],f[i][j][0]+hap[k]}
特殊物品：f[i][j][0]=max{f[i-price[k]][j][0]+hap[k],f[i][j-price[k]][0]+hap[k]}
f[i][j][1]=max{f[i-price[k]][j][1]+hap[k],f[i][j-price[k]][1]+hap[k],f[i][j][0]+hap[k]}
详细见代码：
#include<iostream>
using namespace std;
int v1,v2,n;
int price[305],hap[305],spec[305];
int f[505][55][2];
int main()
{
int test=1;
while(scanf("%d%d%d",&v1,&v2,&n)!=EOF&&(v1||v2||n))
{
int i,j,k,s,total_spec=0;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&price[i],&hap[i],&spec[i]);
if(spec[i]) total_spec+=hap[i];
}
memset(f,-1,sizeof(f));
f[0][0][0]=0;
for(k=1;k<=n;k++)
{
if(!spec[k]) continue;
for(i=v1;i>=0;i--)
for(j=v2;j>=0;j--)
{
f[i][j][1]=-1;
if(f[i][j][0]!=-1&&f[i][j][1]<f[i][j][0]+hap[k])
f[i][j][1]=f[i][j][0]+hap[k];
if(i-price[k]>=0&&f[i-price[k]][j][1]!=-1&&f[i][j][1]<f[i-price[k]][j][1]+hap[k])
f[i][j][1]=f[i-price[k]][j][1]+hap[k];
if(j-price[k]>=0&&f[i][j-price[k]][1]!=-1&&f[i][j][1]<f[i][j-price[k]][1]+hap[k])
f[i][j][1]=f[i][j-price[k]][1]+hap[k];
f[i][j][0]=-1;
if(i-price[k]>=0&&f[i-price[k]][j][0]!=-1&&f[i][j][0]<f[i-price[k]][j][0]+hap[k])
f[i][j][0]=f[i-price[k]][j][0]+hap[k];
if(j-price[k]>=0&&f[i][j-price[k]][0]!=-1&&f[i][j][0]<f[i][j-price[k]][0]+hap[k])
f[i][j][0]=f[i][j-price[k]][0]+hap[k];
}
}
bool flag=false;
for(i=0;i<=v1;i++)
for(j=0;j<=v2;j++)
for(s=0;s<2;s++)
{
if(f[i][j][s]==total_spec)
flag=true;
else f[i][j][s]=-1;
}
if(!flag)
{
printf("Case %d: -1\n\n",test++);
continue;
}
for(k=1;k<=n;k++)
{
if(spec[k]) continue;
for(i=v1;i>=0;i--)
for(j=v2;j>=0;j--)
{
if(f[i][j][0]!=-1&&f[i][j][1]<f[i][j][0]+hap[k])
f[i][j][1]=f[i][j][0]+hap[k];
for(s=0;s<2;s++)
{
if(i-price[k]>=0&&f[i-price[k]][j][s]!=-1&&f[i][j][s]<f[i-price[k]][j][s]+hap[k])
f[i][j][s]=f[i-price[k]][j][s]+hap[k];
if(j-price[k]>=0&&f[i][j-price[k]][s]!=-1&&f[i][j][s]<f[i][j-price[k]][s]+hap[k])
f[i][j][s]=f[i][j-price[k]][s]+hap[k];
}
}
}
int ans=-1;
for(i=0;i<=v1;i++)
for(j=0;j<=v2;j++)
for(s=0;s<2;s++)
if(ans<f[i][j][s])
ans=f[i][j][s];
printf("Case %d: %d\n\n",test++,ans);
}
//system("pause");
return 0;
}
posted on 2010-08-22 11:08
wuxu 阅读(308)
评论(0) 编辑 收藏 引用 所属分类:
动态规划