POJ 1190解题报告

发表于 分类于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

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

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

搜索方向：

对于这道题，在对半径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，所以其最终表面积肯定大于这个估计值。这两种方法可以都用上。

具体实现参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
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;
    }
}