深索優(yōu)化(生日蛋糕).ppt

生日蛋糕,7月17日是MrW的生日，ACM-THU為此要制作一個(gè)體積為n的m層生日每層都是一個(gè)圓柱體。設(shè)從下往上數(shù)第i(1im)層蛋糕是半徑為Ri，高度為hi的圓柱。當(dāng)iRi+1且hi>hi+1。由于要在蛋糕上抹奶油，為盡可能節(jié)約經(jīng)費(fèi)，我們希望蛋糕外表面（最下一層的下底面除外）的面積Q最小(令Q=S)。請(qǐng)編程對(duì)給出的n和m，找出蛋糕的制作方案（適當(dāng)?shù)膔i和hi的值），使S最小。（除Q外，以上所有數(shù)據(jù)皆為正整數(shù)）,輸入有兩行，第一行為n（n10000），表示待制作的蛋糕的體積為n；第二行為m(m20)，表示蛋糕的層數(shù)為m。輸出僅一行，是一個(gè)正整數(shù)S（若無解則S=0）。樣例輸入1002樣例輸出68附：圓柱公式體積V=r2h側(cè)面積A=2rh底面積A=r2,解析法？,數(shù)據(jù)庫(kù)用(i,Ri,Hi,Vi,Si)表示第i層蛋糕的一個(gè)狀態(tài)。其中Ri,Hi分別為第i層蛋糕的半徑和高，Vi,Si分別表示做完第i層蛋糕后剩下的蛋糕體積和當(dāng)前蛋糕的表面積?？梢?，初始狀態(tài)：(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1)目標(biāo)狀態(tài)：(m,Rm,Hm,0,Sm)于是，我們的目標(biāo)是找到一條從初始狀態(tài)到任意目標(biāo)狀態(tài)的路徑，并且Sm最小.擴(kuò)展的規(guī)則(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+1,確定第一層蛋糕的大小根據(jù)上一層蛋糕的大小確定下一層蛋糕該怎么做看是否符合條件1）是否做到了m層2）是否最終體積為03）是否當(dāng)前面積最小若上述條件成立，則保留當(dāng)前最優(yōu)值，否則繼續(xù)做下一層蛋糕，若重做蛋糕,基本算法,Problem-Cake枚舉所有的初始狀態(tài)-第一層蛋糕的大小forR1mtosqrt(n)do/*假設(shè)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)對(duì)每層蛋糕進(jìn)行搜索if(i=m)and(Vi=0)thenbegin計(jì)算面積s;ifsmin,則無論如何都找不到一個(gè)優(yōu)于min的解.因?yàn)橹烙嘞碌牡案怏w積,因此可以估算一下余下側(cè)面積,這樣我們可以就加入如下剪枝條件:if當(dāng)前的表面積+余下的側(cè)面積>當(dāng)前最優(yōu)值thenexit設(shè)已經(jīng)做了i層蛋糕,則還需做m-i層,Si：為第i層蛋糕的側(cè)面積,FSi：余下的側(cè)面積,怎么求FSi?因?yàn)?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>當(dāng)前最優(yōu)值thenexit,可行性剪枝,如果剩下的蛋糕材料太少，不能保證做到m層,那么沒有必要繼續(xù)往下做了，設(shè)，最m層半徑和高都為1，Rm=Hm=1第m-1層半徑和高都為2，Rm-1=Hm-1=2第i+1層半徑和高都為i,Ri=Hi=mi這樣，余下的m-i層的最小體積為,因此,剪枝條件為,ifVi當(dāng)前最優(yōu)值thenexit;剪枝1ifVi<MINithenexit;剪枝2ifViMAXithenexit;剪枝3ifi<mthenforRi+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更新最優(yōu)值Problem-Cake1.計(jì)算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假設(shè)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.,小節(jié),可行性剪枝,剪枝2：ifVi當(dāng)前最優(yōu)值thenexit,剪枝原則,正確、高效,深度搜索消耗時(shí)間每個(gè)節(jié)點(diǎn)操作系數(shù)節(jié)點(diǎn)個(gè)數(shù),優(yōu)化1）減少節(jié)點(diǎn)個(gè)數(shù)這就是剪枝優(yōu)化；2）減少每個(gè)節(jié)點(diǎn)的操作系數(shù)即程序操作量。,