《深索优化(生日蛋糕)》由会员分享，可在线阅读，更多相关《深索优化(生日蛋糕)（15页珍藏版）》请在金锄头文库上搜索。
1、生日蛋糕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）。 样例输入
2、 100 2 样例输出 68 附：圆柱公式 体积V=r2h 侧面积A=2rh 底面积A=r2解析法？ o数据库 用( 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最小. o扩展的规则( i , Ri , Hi , Vi , Si ) ( i+1,Ri+1,H
3、i+1,Vi+1,Si+1) 满足:（1） Ri Ri+1（2） Hi Hi+1（3） Vi+1 = Vi - Ri+1* Ri+1* Hi+1（4） Si+1 = Si + 2 * Ri+1* Hi+1o确定第一层蛋糕的大小o根据上一层蛋糕的大小确定下一层蛋糕该怎 么做o看是否符合条件1）是否做到了m层2）是否最终体积为03）是否当前面积最小o若上述条件成立，则保留当前最优值，否则 继续做下一层蛋糕，若重做蛋糕基本算法oProblem-Cake 枚举所有的初始状态 - 第一层蛋糕的大小for R1m to sqrt ( n ) do /*假设 H1=1 ，只做一层蛋糕 */for H1n d
4、iv (R1*R1) downto m dobeginS1=2 * R1* H1+ R1* R1V1=n - R1* R1 * H1Search (1, R1, H1, S1, V1)end;确定第一层蛋糕的大小oSearch (i, Ri , Hi , Si , Vi)对每层蛋糕进行搜索 if (i=m) and (Vi =0) then begin 计算面积s; if smin,则无论如何都找不到一个优于min的解.o因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加 入如下剪枝条件:if 当前的表面积 + 余下的側面积 当前最优值 then exit设已经做了i层蛋糕,
5、则还需做m-i层, Si：为第i层蛋糕的侧面积, FSi：余下的侧面积,怎么求FSi ?因为:2Vi= 2Ri+1 * Ri+1 * Hi+1 + .+ 2Rm * Rm * Hm= Ri+1 * Si+1 + .+ Rm * Sm Ri+1 * (Si+1+ .+ Sm)= Ri+1 * FSi 所以:FSi 2Vi / Ri+1 因此剪枝条件为：if Si-1 + 2 * Vi-1 / Ri 当前最优值 then exit可行性剪枝o如果剩下的蛋糕材料太少，不能保证做到m层,那么没有 必要继续往下做了，设， 最m层半径和高都为1，Rm=Hm=1 第m-1层半径和高都为2，Rm-1=Hm-1
6、=2第 i +1层半径和高都为i, Ri = Hi = m i 这样， 余下的m-i层的最小体积为因此,剪枝条件为,if Vi当前最优值 then exit; 剪枝1if Vi 当前最优值 then exito剪枝原则 正确、高效深度搜索消耗时间 每个节点操作系数 节点个数优化1）减少节点个数这就是剪枝优化；2）减少每个节点的操作系数即程序操作量。NM 原程 序加入第一个剪 枝 1000 4 0.280.06 3000 8 0.330.06 4000 8 5.940.50NM加入第一个剪 枝加入所有剪 枝 4000 80.500.06 4999 82.440.06 6000 415.390.11
