深索优化(生日蛋糕).ppt

生日蛋糕,7月17日是MrW的生日，ACM-THU为此要制作一个体积为n的m层生日每层都是一个圆柱体。设从下往上数第i(1im)层蛋糕是半径为Ri，高度为hi的圆柱。当iRi+1且hihi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小(令Q=S)。请编程对给出的n和m，找出蛋糕的制作方案（适当的ri和hi的值），使S最小。（除Q外，以上所有数据皆为正整数）,输入有两行，第一行为n（n10000），表示待制作的蛋糕的体积为n；第二行为m(m20)，表示蛋糕的层数为m。输出仅一行，是一个正整数S（若无解则S=0）。样例输入1002样例输出68附：圆柱公式体积V=r2h侧面积A=2rh底面积A=r2,解析法？,数据库用(i,Ri,Hi,Vi,Si)表示第i层蛋糕的一个状态。其中Ri,Hi分别为第i层蛋糕的半径和高，Vi,Si分别表示做完第i层蛋糕后剩下的蛋糕体积和当前蛋糕的表面积。可见，初始状态：(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1)目标状态：(m,Rm,Hm,0,Sm)于是，我们的目标是找到一条从初始状态到任意目标状态的路径，并且Sm最小.扩展的规则(i,Ri,Hi,Vi,Si)(i+1,Ri+1,Hi+1,Vi+1,Si+1)满足:（1）RiRi+1（2）HiHi+1（3）Vi+1=Vi-Ri+1*Ri+1*Hi+1（4）Si+1=Si+2*Ri+1*Hi+1,确定第一层蛋糕的大小根据上一层蛋糕的大小确定下一层蛋糕该怎么做看是否符合条件1）是否做到了m层2）是否最终体积为03）是否当前面积最小若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕,基本算法,Problem-Cake枚举所有的初始状态-第一层蛋糕的大小forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/forH1ndiv(R1*R1)downtomdobeginS1=2*R1*H1+R1*R1V1=n-R1*R1*H1Search(1,R1,H1,S1,V1)end;,确定第一层蛋糕的大小,Search(i,Ri,Hi,Si,Vi)对每层蛋糕进行搜索if(i=m)and(Vi=0)thenbegin计算面积s;ifsmin,则无论如何都找不到一个优于min的解.因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件:if当前的表面积+余下的側面积当前最优值thenexit设已经做了i层蛋糕,则还需做m-i层,Si：为第i层蛋糕的侧面积,FSi：余下的侧面积,怎么求FSi?因为:2Vi=2Ri+1*Ri+1*Hi+1+.+2Rm*Rm*Hm=Ri+1*Si+1+.+Rm*SmRi+1*(Si+1+.+Sm)=Ri+1*FSi所以:FSi2Vi/Ri+1因此剪枝条件为：ifSi-1+2*Vi-1/Ri当前最优值thenexit,可行性剪枝,如果剩下的蛋糕材料太少，不能保证做到m层,那么没有必要继续往下做了，设，最m层半径和高都为1，Rm=Hm=1第m-1层半径和高都为2，Rm-1=Hm-1=2第i+1层半径和高都为i,Ri=Hi=mi这样，余下的m-i层的最小体积为,因此,剪枝条件为,ifVi当前最优值thenexit;剪枝1ifViMINithenexit;剪枝2ifViMAXithenexit;剪枝3ifimthenforRi+1Ridowntom-i+1forHi+1min(Vidiv(Ri+1*Ri+1),Hi)downtom-i+1Si+1Si+2*Ri+1*Hi+1Vi+1Vi-Ri+1*Ri+1*Hi+1Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)ElseifVi=0then更新最优值Problem-Cake1.计算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假设H1=1，只做一层蛋糕*/3.forH1ndiv(R1*R1)downtomdo4.S1=2*R1*H1+R1*R15.V1=n-R1*R1*H16.Search(1,R1,H1,S1,V1)7.,小节,可行性剪枝,剪枝2：ifVi当前最优值thenexit,剪枝原则,正确、高效,深度搜索消耗时间每个节点操作系数节点个数,优化1）减少节点个数这就是剪枝优化；2）减少每个节点的操作系数即程序操作量。,