深索優(yōu)化(生日蛋糕).ppt
生日蛋糕,7月17日是MrW的生日,ACM-THU為此要制作一個體積為n的m層生日每層都是一個圓柱體。設(shè)從下往上數(shù)第i(1im)層蛋糕是半徑為Ri,高度為hi的圓柱。當(dāng)iRi+1且hi>hi+1。由于要在蛋糕上抹奶油,為盡可能節(jié)約經(jīng)費(fèi),我們希望蛋糕外表面(最下一層的下底面除外)的面積Q最小(令Q=S)。請編程對給出的n和m,找出蛋糕的制作方案(適當(dāng)?shù)膔i和hi的值),使S最小。(除Q外,以上所有數(shù)據(jù)皆為正整數(shù)),輸入有兩行,第一行為n(n10000),表示待制作的蛋糕的體積為n;第二行為m(m20),表示蛋糕的層數(shù)為m。輸出僅一行,是一個正整數(shù)S(若無解則S=0)。樣例輸入1002樣例輸出68附:圓柱公式體積V=r2h側(cè)面積A=2rh底面積A=r2,解析法?,數(shù)據(jù)庫用(i,Ri,Hi,Vi,Si)表示第i層蛋糕的一個狀態(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)對每層蛋糕進(jìn)行搜索if(i=m)and(Vi=0)thenbegin計算面積s;ifsmin,則無論如何都找不到一個優(yōu)于min的解.因為知道余下的蛋糕體積,因此可以估算一下余下側(cè)面積,這樣我們可以就加入如下剪枝條件:if當(dāng)前的表面積+余下的側(cè)面積>當(dāng)前最優(yōu)值thenexit設(shè)已經(jīng)做了i層蛋糕,則還需做m-i層,Si:為第i層蛋糕的側(cè)面積,FSi:余下的側(cè)面積,怎么求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>當(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.計算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,剪枝原則,正確、高效,深度搜索消耗時間每個節(jié)點操作系數(shù)節(jié)點個數(shù),優(yōu)化1)減少節(jié)點個數(shù)這就是剪枝優(yōu)化;2)減少每個節(jié)點的操作系數(shù)即程序操作量。,