先DP缩小范围,后枚举。
题目大意:背包问题变种。有三种物品,分别对应有weight,size,vlaue,有n个背包,每个背包也有对应的可容纳weight和可容纳size。用所有的背包,在weight和size的限制下,能得到三种物品的数量x,y,z,ans=max(x*vx+y*vy+z*vz)+extra,这里有一个比较特殊的地方在于三种物品按某一数量组合,可以得到“套装”,会有额外的价值。
分析:显然,需要先得到可能是最优解的x,y,z的各种组合,再通过比较得到的最大总value。在相同x,y的情况下,我们总是尽量使z最大。直接用搜索必然很耗时间,这里我们用DP来求x,y组合对应的z的最大值。状态state[m][x][y]表示在使用1-m这m个背包的情况下,取x,y值时,对应的z的最大值。即有状态方程state[m][x][y]=max(state[m-1][x'][y']+zi),其中(xi+x'=x,yi+y'=y,xi*wx+yi*wy+zi*wz<=w[m],xi*sx+yi*sy+zi*sz<=s[m])(因为要求zi要尽量大,所以同时会有xi*wx+yi*wy+(zi+1)*wz>w[m],xi*sx+yi*sy+(zi+1)*sz>s[m]).
最后ans=max(cal_value(x,y,state[n][x][y]))。
以下是原代码,为了节省空间,使用了滚动数组。
memset(state[0],0,sizeof(state[0]));
int ix,iy,iz,tempx,tempy,temp;
maxx=maxy=0;
for(int i=1;i<=n;i++)
{
memset(state[1],0xff,sizeof(state[1]));
tempx=min(w[i]/wx,s[i]/sx);
for(ix=0;ix<=tempx;ix++)
{
tempy=min((w[i]-ix*wx)/wy,(s[i]-ix*sx)/sy);
for(iy=0;iy<=tempy;iy++)
{
iz=min((w[i]-ix*wx-iy*wy)/wz,(s[i]-ix*sx-iy*sy)/sz);
for(int a=0;a<=maxx;a++)
{
for(int b=0;b<=maxy;b++)
{
if(state[0][a][b]>=0)
{
rg(state[1][a+ix][b+iy],state[0][a][b]+iz);
}
}
}
}
if(ix==0) temp=tempy;
}
memcpy(state[0],state[1],sizeof(state[0]));
maxx+=tempx;
maxy+=temp;
}
}
void Print()
{
def-=c1*vx+c2*vy+c3*vz;
int ans=0;
for(int a=0;a<=maxx;a++)
{
for(int b=0;b<=maxy;b++)
{
if(state[1][a][b]>=0)
{
rg(ans,a*vx+b*vy+state[1][a][b]*vz+(def>0?def*min(a/c1,min(b/c2,state[1][a][b]/c3)):0));
}
}
}
if(cs++) printf("/n");
printf("Case %d: %d/n",cs,ans);
}
需要指出的是,最后的输出printf("Case %d: %d/n",cs,ans),在冒号后有一个空格,我因为没注意到这个问题,之前一直wa。囧。