POJ 1190解题报告

生日蛋糕问题是一道很典型的题目,让我对剪枝优化有了更深刻的理解。

这道题的剪枝优化应该从三个方面入手,搜索方向、体积、表面积。我总结了一下,这三种剪枝很有代表性,搜索方向是搜索技巧上的剪枝;体积上的优化是将解决问题过程中不符合要求的方案的剪枝,如果搜索时发现,从当前的方案继续搜索是不可能搜索出结果的,就可以直接回溯了;而表面积上的优化,是出于对问题结果的分析的剪枝,如果是搜索最优方案的题目,不能搜索出比当前的最优方案更优的方案时,是可以回溯的。

搜索方向:

对于这道题,在对半径R和高度H枚举时,应该考虑是从大到小,还是从小到大。由于一开始时并没有思考这个问题,才导致一直超时。对于所有的搜索问题,都应该从这里入手:什么样的搜索方向更为合理。

因为

体积V=R1*R1*H1+R2*R2*H2+….+Rn*Rn*Hn

表面积S=2*R1*H1+2*R2*H2+….+2* Rn*Hn

因为V是固定的,所以S和R成反比。R越大,S越小。

可以确定在枚举R时要从大到小,这样会先找到S最小的方案。

个人认为在枚举H时应该从小到大,但是在POJ上测试并没有明显的效果。因为体积V固定,要想让每一层的蛋糕的R都能取到相对大的值,那么每一层蛋糕的H优先选取小的值,会更快找到S最小的方案。

体积优化:

应该是最先想到的优化,每一层的蛋糕R和H都有最小值,那么最小体积应该求出,可以打表实现。下面两种情况是可以剪掉的:

1.  剩余层的最小体积加上当前的体积大于总的体积

2.  剩余层的最大体积加上当前的体积大于总的体积

剩余层的最大体积是可以估计出来的,R和H越大,体积越大,在当前层的R和H的基础上,剩余层的R和H都选择最大值。

表面积优化:

因为题目的要求是最小的S,所以下面的情况可以剪掉:

剩余层的最小表面积加上当前的表面积大于已经找到的最小表面积。

对于剩余层的最小表面积的估计,有两种方法。首先可以想到的是,因为每一层的R和H都有最小值,那么可以预先求得其表面积。

参考了网上的各种代码后,才得出了另一种的估计方法:上面提到,S和R’成反比,那么用剩余的体积V’除以当前层的半径R可以求得估计值,由于剩余层的半径必然小于R,所以其最终表面积肯定大于这个估计值。这两种方法可以都用上。

具体实现参考代码:

/*
poj 1190 生日蛋糕
*/
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int data[21];
int mArea[21];
int minArea,N,M;
int lastR,lastH;

int func(int R,int H,int step)
//求第step层的半径为R、H时,1到step层的最大体积
{
int ra=R,ha=H,sum=0;
for(int i=step;i>=1;i--)
{
sum+=ra*ra*ha;
ra--;ha--;
}
return sum;
}

int min(int a,int b)
{
return (a<b?a:b);
}

void DFS(int step,int R,int H,int volumn,int area)
{
if(step==0)
{
if(volumn==N && area<minArea)
minArea=area;
return;
}
if(volumn+data[step]>N) return; //剩余层的最小体积加上当前的体积大于总的体积
if(area+mArea[step]>=minArea || 2*(N-volumn)/R+area>=minArea) return; //表面积比最小值大
intleft=N-volumn-data[step-1];
int maxR=min(R-1,ceil(sqrt(left*1.0/step))); //对R的初始值进行优化
for(int i=maxR;i>=step;i--) //R从大到小
{
if(step==M) area=i*i;
intmaxH=min(left/i/i,H-1);
for(int j=step;j<=maxH;j++) //H从小到大
{
if(func(i-1,j-1,step-1)+volumn+i*i*j<N) continue; //剩余层的最大体积加上当前的体积小于总的体积
DFS(step-1,i,j,volumn+i*i*j,area+2*i*j);
}
}
}

int main()
{
// ifstream cin("test.txt");
data[0]=mArea[0]=0;
for(int i=1;i<=20;i++) //初始化
{
data[i]=data[i-1]+i*i*i;
mArea[i]=mArea[i-1]+2*i*i;
}
for(;cin>>N>>M;)
{
minArea=0x7fffffff;
DFS(M,N+1,N+1,0,0);
cout<<(minArea==0x7fffffff?0:minArea)<<endl;
}
}