生日蛋糕生日蛋糕 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解析法？ 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,Hi+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）是否最终体积为0 3）是否当前面积最小o若上述条件成立，则保留当前最优值，否则继续做下一层蛋糕，若重做蛋糕基本算法oProblem-Cake枚举所有的初始状态 - 第一层蛋糕的大小 for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ for H1n div (R1*R1) downto m do begin S1=2 * R1* H1+ R1* R1 V1=n - R1* R1 * H1 Search (1, R1, H1, S1, V1) end;确定第一层蛋糕的大小oSearch (i, Ri , Hi , Si , Vi) 对每层蛋糕进行搜索if (i=m) and (Vi =0) then begin 计算面积s; if smin,smin,则无论如何都找不到一个优于则无论如何都找不到一个优于minmin的解的解. .o因为知道余下的蛋糕体积,因此可以估算一下余下侧面积,这样我们可以就加入如下剪枝条件: if if 当前的表面积当前的表面积 + + 余下的側面积余下的側面积 当前最优当前最优值值 then exitthen exit 设已经做了i层蛋糕,则还需做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=2 第 i +1层半径和高都为i, Ri = Hi = m i 这样， 余下的m-i层的最小体积为 因此,剪枝条件为, if Vi当前最优值当前最优值 then exit; 剪枝剪枝1 if Vi MINi then exit; 剪枝剪枝2 if Vi MAXi then exit; 剪枝剪枝3 if im then for Ri + 1 Ri downto m-i+1 for Hi + 1min(Vi div (Ri + 1*Ri + 1), Hi) downto m-i+1 Si + 1Si + 2 * Ri + 1* Hi + 1 Vi + 1Vi - Ri + 1* Ri + 1* Hi + 1 Search ( i+1, Ri + 1, Hi + 1, Si + 1,Vi + 1) Else if Vi =0 then 更新最优值更新最优值Problem-Cake 1. 计算MINi和MAXi R,H ; 2. for R1m to sqrt ( n ) do /*假设 H1=1，只做一层蛋糕 */ 3. for H1n div (R1*R1) downto m do 4. S1=2 * R1* H1+ R1* R1 5. V1=n - R1* R1 * H1 6. Search (1, R1, H1, S1, V1) 7. 小节o可行性剪枝 剪枝2：if Vi当前最优值 then exito剪枝原则 正确、高效深度搜索消耗时间深度搜索消耗时间 每个节点操作系数每个节点操作系数 节点个数节点个数 优化 1）减少节点个数这就是剪枝优化剪枝优化； 2）减少每个节点的操作系数即程序操作量程序操作量。NM 原程序 加入第一个剪枝1000 4 0.280.063000 8 0.330.064000 8 5.940.50NM加入第一个剪枝 加入所有剪枝4000 80.500.064999 82.440.066000 415.390.11