深度搜尋剪枝——生日蛋糕問題

Description：

7月17日是Mr.W的生日，ACM-THU為此要制作一個體積為N*pi的M層生日蛋糕，每層都是一個圓柱體。 設從下往上數第i(1 <= i <= M)層蛋糕是半徑為Ri, 高度為Hi的圓柱。當i < M時，要求Ri > Ri+1且Hi > Hi+1。

由于要在蛋糕上抹奶油，為盡可能節約經費，我們希望蛋糕外表面（最下一層的下底面除外）的面積Q最小。

令Q = S*pi

請程式設計對給出的N和M，找出蛋糕的制作方案（适當的Ri和Hi的值），使S最小。

（除Q外，以上所有資料皆為正整數）

Input：

有兩行，第一行為N（N <= 10000），表示待制作的蛋糕的體積為Nπ；第二行為M(M <= 20)，表示蛋糕的層數為M。

Output：

僅一行，是一個正整數S（若無解則S = 0）。 Time Limit：1000MS       Memory Limit： 10000K

Sample Input

100
2      

Sample Output      

68      

問題分析：      

source：      

#include <iostream>
#include <cmath>
using namespace std;
int n,m,minv[21],mins[21];  
                            //V=n*pi  m 層數 自頂向下1.2.3...m  
                            //minv[i]表示i層到0層加起來的最小總體積 minvs 最小表面積
const int inf=1000000000;   // inf 足夠大就可以 int(32)  -2^31~2^31-1=2147483647  
int best=inf;				//best 最小表面積

void DFS(int depth,int sumv,int sums,int r,int h) //深度優先搜尋 自底m向上搜尋 r h表示目前層得半徑和高度
												  //sumv已經用的總體積 sums已經生成的總表面積
{
	if(0==depth)
	{
		if(sumv==n&&sums<best)           //搜尋完成 更新最小表面積best
		{
			best=sums;
		}
		return;
	}
	// 三個剪枝條件：
	//1、已經搜尋過的體積加上還未搜尋過的最小體積不能比總體積n 大
    //2、已經搜尋過的表面積加上還未搜尋過的最小表面積不能比之前的最小總表面積best 大 
    //3、n-sumv既所剩體積記作dv 還需要的表面積為s
	//s=2*ri*hi+2*r(i-1)*h(i-1)+... >=2*ri*hi*ri/r+2*r(i-1)*h(i-1)*r(i-1)/r+...
	//	                            =2*dv/r（i從depth-1取,r為目前半徑 ri/r<1）
    // 是以得到還需要的最小表面積s=2*(n-sumv)/r，如果最小的s和已經搜尋過的表面積sums依然比best大 就不用繼續搜尋了
	if(sumv+minv[depth-1]>n||sums+mins[depth-1]>best||sums+2*(n-sumv)/r>=best)  //剪枝如上所述
		return;
	for( int i=r-1;i>=depth;i--)    //遞減順序枚舉depth層半徑的每一個可能值,這裡第depth層的半徑最小值為depth
	{
		if(depth==m)
			sums=i*i;      //俯視蛋糕底面積作為外表面積的初始值(總的上表面積,以後隻需計算側面積)
		int maxh=min((n-sumv-minv[depth-1])/(i*i),h-1);  
		                 //maxh最大高度,即depth層蛋糕高度的上限,(n-sumv-minv[dep-1])表示第depth層最大的體積
		for(int j=maxh;j>=depth;j--)    //同理,第depth層的最小高度值為depth
		{
			DFS(depth-1,sumv+i*i*j,sums+2*i*j,i,j);  //遞歸搜尋子狀态
		}
	}
}
int main(void)
{
	cout<<"input V <=10000 :"<<endl;
	cin>>n;
	cout<<"input M <=20 :"<<endl;
	cin>>m;
	int rmax=(int)sqrt((double)n); //rmax初始半徑 底層半徑 最大值為sqrt(n)
	int hmax=n;                    //hmax初始高度 高度最大為 n
	minv[0]=mins[0]=0;
	for(int i=1;i<=m;i++)
	{                              //初始化minv和mins數組
		minv[i]=minv[i-1]+i*i*i;   //從頂層(即第1層)到第i層的最小體積minv[i]成立時第j層的半徑和高度都為j
		mins[i]=mins[i-1]+2*i*i;
	}
	DFS(m,0,0,rmax,hmax);
	//DFS(m,0,0,n+1,n+1);
	if(best==inf)
		best=0;        //無解
	if(best==0)
		cout<<"No solution"<<endl;
	else
		cout<<"The min Q ="<<best<<"*pi"<<endl;
	return 0;
}