石子合并問(wèn)題報(bào)告

1、每次只能1行是得順時(shí)針次序輸入輸出范石子合并（動(dòng)態(tài)規(guī)劃）詳細(xì)解題報(bào)告007-02-2514:58試題在一個(gè)園形操場(chǎng)的四周擺放N堆石子（NW100）,現(xiàn)要將石子有次序地合并成一堆。規(guī)定選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)，記為該次合并的得分。編一程序，由文件讀入堆數(shù)N及每堆的石子數(shù)（<20）,選擇一種合并石子的方案，使得做N1次合并，得分的總和最?。贿x擇一種合并石子的方案，使得做N1次合并，得分的總和最大。例如，所示的4堆石子，每堆石子數(shù)（從最上面的一堆數(shù)起，順時(shí)針數(shù)）依次為4594。則3次合并得分總和最小的方案：8+13+22=43得分最大的方案為：14+18+22=54輸入

2、數(shù)據(jù)：文件名由鍵盤(pán)輸入，該文件內(nèi)容為：第一行為石子堆數(shù)N；第二行為每堆的石子數(shù)，每?jī)蓚€(gè)數(shù)之間用一個(gè)空格符分隔。輸出數(shù)據(jù)：輸出文件名為output.txt從第1至第N行為得分最小的合并方案。第N+1行是空行。從第N+2行到第2N+分最大合并方案。每種合并方案用N行表示，其中第i行（1<i<N）表示第i次合并前各堆的石子數(shù)（依輸出，哪一堆先輸出均可）。要求將待合并的兩堆石子數(shù)以相應(yīng)的負(fù)數(shù)表示，以便標(biāo)識(shí)4594輸出文件內(nèi)容：-8-5913-922-94-4-94-44-54-14-4-18二算法分析競(jìng)賽中多數(shù)選手都不約而同地采用了盡可能逼近目標(biāo)的貪心法來(lái)逐次合并：從最上面的一堆開(kāi)始，沿順

3、時(shí)針?lè)较蚺懦梢粋€(gè)序列。第一次選得分最?。ㄗ畲螅┑南噜弮啥押喜?，形成新的一堆；接下來(lái)，在N-1堆中選得分最?。ㄗ畲螅┑南噜弮啥押喜?，依次類(lèi)推，直至所有石子經(jīng)N-1次合并后形成一堆。要求選擇一種合并石子的方案，使得做5次合并，得分的總和最小按照貪心法，合并的過(guò)程如下：每次合并得分第一次合并346542?>5第二次合并54654->9第三次合并9654->9第四次合并969?>15第五次合并159?>2424總得分=5+9+9+15+24=62每次合并得分第一次合并346542->7第二次合并76542?>13第三次合并13542->6F1356-&

4、gt;111311->24但是當(dāng)我們仔細(xì)琢磨后，可得出另一個(gè)合并石子的方總得分=7+6+11+13+24=61顯然，后者比貪心法得出的合并方案更優(yōu)。題目中的示例故意造成一個(gè)貪心法解題的假像，誘使讀者進(jìn)入“陷阱”。為了幫助讀者從這個(gè)“陷阱”里走出來(lái)，我們先來(lái)明確一個(gè)問(wèn)題：1最佳合并過(guò)程符合最佳原理使用貪心法至所以可能出錯(cuò)，是因?yàn)槊恳淮芜x擇得分最小（最大）的相鄰兩堆合并，不一定保證余下的合并過(guò)程能導(dǎo)致最優(yōu)解。聰明的讀者馬上會(huì)想到一種理想的假設(shè)：如果N1次合并的全局最優(yōu)解包含了每一次合并的子問(wèn)題的最優(yōu)解，那么經(jīng)這樣的N1次合并后的得分總和必然是最優(yōu)的。例如上例中第五次合并石子數(shù)分別為13和11

5、的相鄰兩堆。這兩堆石頭分別由最初的第1,2,3堆（石頭數(shù)分別為3,4,6）和第4,5,6堆（石頭數(shù)分別為5,4,2）經(jīng)4次合并后形成的。于是問(wèn)題又歸結(jié)為如何使得這兩個(gè)子序列的N2次合并的得分總和最優(yōu)。為了實(shí)現(xiàn)這一目標(biāo),我們將第1個(gè)序列又一分為二：第1、2堆構(gòu)成子序列1,第3堆為子序列2。第一次合并子序列1中的兩堆,得分7；第二次再將之與子序列2的一堆合并,得分13。顯然對(duì)于第1個(gè)子序列來(lái)說(shuō),這樣的合并方案是最優(yōu)的。同樣,我們將第2個(gè)子序列也一分為二；第4堆為子序列1,第5,6堆構(gòu)成子序列2。第三次合并子序列2中的2堆,得分6；第四次再將之與子序列1中的一堆合并,得分13。顯然對(duì)于第二個(gè)子序列來(lái)

6、說(shuō),這樣的合并方案也是最優(yōu)的。由此得出一個(gè)結(jié)論一一6堆石子經(jīng)過(guò)這樣的5次合并后,得分的總和最小。我們把每一次合并劃分為階段,當(dāng)前階段中計(jì)算出的得分和作為狀態(tài),如何在前一次合并的基礎(chǔ)上定義一個(gè)能使目前得分總和最大的合并方案作為一次決策。很顯然,某階段的狀態(tài)給定后,則以后各階段的決策不受這階段以前各段狀態(tài)的影響。這種無(wú)后效性的性質(zhì)符最佳原理,因此可以用動(dòng)態(tài)規(guī)劃的算法求解第N堆、第1堆、第2堆第N堆、第1堆、，、第N1堆它的最佳合并N)動(dòng)態(tài)規(guī)劃的方,、第N堆數(shù)起，順時(shí)針數(shù)22.動(dòng)態(tài)規(guī)劃的方向和初值的設(shè)定這些石子堆子序列包括：采用動(dòng)態(tài)規(guī)劃求解的關(guān)鍵是確定所有石子堆子序列的最佳合并方案。第1堆、第2堆、

7、第2堆、第3堆、，、第N堆、第1堆第1堆、第2堆、第3堆、第2堆、第3堆、第4堆、第1堆、,、第N堆第2堆、,、第N堆、第1堆為了便于運(yùn)算，我們用i,j表示一個(gè)從第i堆數(shù)起，順時(shí)針數(shù)j堆時(shí)的子序列第i堆、第i+1堆、，,、第(i+j1)modn堆方案包括兩個(gè)信息： 在該子序列的各堆石子合并成一堆的過(guò)程中，各次合并得分的總和；形成最佳得分和的子序列1和子序列2。由于兩個(gè)子序列是相鄰的，因此只需記住子序列1的堆數(shù)；設(shè)fi,j將子序列i,j丨中的j堆石子合并成一堆的最佳得分和；ci,j一一將i,jI一分為二，其中子序列1的堆數(shù)；(1<i<N,1<j<N)顯然，對(duì)每一堆石子來(lái)說(shuō)

8、，它的fi,1=0ci,1=0(1<i<N)對(duì)于子序列i,j丨來(lái)說(shuō)，若求最小得分總和，fi,j的初始值為若求最大得分總和，fi,j的初始值為0。(1wi<N,2<j<向是順推(即從上而下)。先考慮含二堆石子的N個(gè)子序列(各子序列分別從第1堆、第2堆、堆）的合并方案f1,2，f2,2，,fN,2c1,2，c2,2，”,cN,2、第N堆數(shù)起，順時(shí)針數(shù)3堆）的合并方案,，、第N堆數(shù)起，順時(shí)針數(shù)N堆）的合并方案然后考慮含三堆石子的N個(gè)子序列（各子序列分別從第1堆、第2堆、f1，3，f2，3，fN,3c1，3，c2，3，,，cN,3依次類(lèi)推，直至考慮了含N堆石子的N個(gè)子序列

9、（各子序列分別從第1堆、第2堆、fNfNc最2,i后，出發(fā)倒推合并過(guò)程。3.動(dòng)態(tài)規(guī)劃方程和倒推合并過(guò)程對(duì)子序列i，j最后一次合并，其得分為第i堆數(shù)起，順時(shí)針數(shù)j堆的石子總數(shù)t。被合并的兩堆石子是由子序列i，k和（i+k-1）modn+1,j-k（1<k<j1）經(jīng)有限次合并形成的。為了求出最佳合并方案中的k值，我們定義一個(gè)動(dòng)態(tài)規(guī)劃方程：當(dāng)求最大得分總和時(shí)fi，j=maxfi，k+fx，j-k+tII.廠、CLI,Jj=kIfLI,Jj(2WjWn,1WiWn)=fCi?k+fx，j-k+t當(dāng)求最小得分總和時(shí)fi,j=minfi,k+fx,jk+t1<k<j1ci,j=k|

10、fi,j=fi,k+fx,j-k+t(2WjWn,1WiWn)其中x=(i+k1)modn+1,即第i堆數(shù)起，順時(shí)針數(shù)k+1堆的堆序號(hào)例如對(duì)上面例子中的6(346542)堆石子，按動(dòng)態(tài)規(guī)劃方程順推最小得分和f1，2=72，2=10f3,2=11c1，2=12，2=1c3，2=1f4，2=95，2=6f6，2=5c4，2=15，2=c6，2=1例如對(duì)上面例子中的6(346542)堆石子，按動(dòng)態(tài)規(guī)劃方程順推最小得分和f1，2=72，2=10f3,2=11c1，2=12，2=1c3，2=1f4，2=95，2=6f6，2=5c4，2=15，2=c6，2=1依次得出含二堆石子的6個(gè)子序列的合并方案含三堆

11、石子的646f22，f1，c1，3=23=2f4，3=1f5c4，3=15，2)個(gè)子序列的合并方案3=25f3，3=24=2c3，3=13=4f6，3=14=1c6，3=2含四堆石子的6(346542)個(gè)子序列的合并方案f1,4=36f2,4=38f3,4=34c1,4=2c2,4=2c3,4=1f4,4=28f5,4=26f6,4=29c4,4=1c5,4=2c6,4=3含五堆石子的6(346542)個(gè)子序列的合并方案f1，5=51f2,5=48f3,5=45c1，5=3c2，5=2c3，5=2f4，5=41f5，5=43f6，5=45c4，5=2c5，5=3c6，5=3含六堆石子的6(3含

12、六堆石子的6(342)個(gè)子序列的合并方案=61f2，6=62f6=611，6=3c2，6=2c6=2f4，6=61f6=61f6，6=62c4，6=3c6=4c6，6=3f1,6丨是f1,6，f2,6，,f6,6丨中的最小值，表明最小得分和是由序列1,6丨經(jīng)5次合并得出的。我們從這個(gè)序列出發(fā)，按下述方法倒推合并過(guò)程：由c1,6=3可知，第5次合并的兩堆石子分別由子序列1,3和子序列4,3經(jīng)4次合并后得出。其中c1,3=2可知由子序列1,3合并成的一堆石子是由子序列1,2和第三堆合并而來(lái)的。而c1,2=1,以表明了子序列1,2丨的合并方案是第1堆合并第2堆。由此倒推回去，得出第1,第2次合并的方

13、案，每次合并得分第一次合并346,->7第二次合并76,->1313,子序列1,3丨經(jīng)2次合并后合并成1堆，2次合并的得分和=7+13=20。c4,3=1,可知由子序列4,3合并成的一堆石子是由第4堆和子序列5,2合并而來(lái)的。而c5,2=1,又表明了子序列5,2丨的合并方案是第5堆合并第6堆。由此倒推回去，得出第3、第4次合并的方案每次合并得分：第三次合并,542->6第四次合并,56->11,11子序列4,3經(jīng)2次合并后合并成1堆,2次合并的得分和=6+11=17。第五次合并是將最后兩堆合并成1堆,該次合并的得分為24。顯然,上述5次合并的得分總和為最小20+17+2

14、4=61上述倒推過(guò)程,可由一個(gè)print（子序列）的遞歸算法描述procedureprint（i,j）beginifj<>1then繼續(xù)倒推合并過(guò)程beginprint（i,ci,j；倒推子序列1的合并過(guò)程print（i+ci,j1modn+1,jci,j）倒推子序列2的合并過(guò)程forK:=1toNdo輸出當(dāng)前被合并的兩堆石子if（第K堆石子未從圈內(nèi)去除）thenbeginif（K=i）or（K=X）then置第K堆石子待合并標(biāo)志else第K堆石子未被合并；end;then第i堆石子數(shù)?第i堆石子數(shù)+第X堆石子數(shù)；將第X堆石子從圈內(nèi)去除；end;thenend;print例如，調(diào)用

15、print（Cl,6）后的結(jié)果如下：print（1,6）printprintprint（1,3）（4,3）print（1,2）print（3,1）print（4,1）print（5,2）print（1,1print（2,1）print（5,1print（6,1）（圖6.2-5）其中回溯至顯示34654顯示76542顯示13542顯示1356顯示1311注:調(diào)用print過(guò)程后，應(yīng)顯示6堆石子的總數(shù)作為第5次合并的得分ProgramStones;TypeNode=Record當(dāng)前序列的合并方案c:Longint;得分和d:Byte子序列1的堆數(shù)End;SumType=Array仁100,1.10

16、0ofLongint;sumtypei,j-子序列i,j的石子總數(shù)VarList:Array1.100,1.100ofNode;listi,j-子序列i,j的合并方案Date,Dt:Array1.100ofInteger;Datei-第i堆石子數(shù),Dt-暫存DateSum:ASumType;sumAi,j-指向子序列i,j的石子總數(shù)的指針F:Text;文件變量Fn:String;文件名串N,i,j:Integer;N-石子堆數(shù),i,j-循環(huán)變量ProcedurePrint(i,j:Byte);遞歸打印子序列i,j的合并過(guò)程Vark,x:Shortint;k-循環(huán)變量；x-子序列2中首堆石子的序

17、號(hào)BeginIfj<>1ThenBegin繼續(xù)倒推合并過(guò)程Print(i,Listi,j.d);倒推子序列1的合并過(guò)程x:=(i+Listi,j.d-1)ModN+1;求子序列2中首堆石子的序號(hào)Print(x,j-Listi,j.d);倒推子序列2的合并過(guò)程Fork:=1toNDo輸出當(dāng)前合并第i堆，第x堆石子的方案IfDatek>0ThenBeginIf(i=k)or(x=k)ThenWrite(F,-Datek,'')ElseWrite(F,Datek,'')End;ThenWriteln(F);輸出換行符Datei:=Datei+Date

18、x;原第i堆和第x堆合并成第i堆Datex:=-Datex將原第x堆從圈內(nèi)去除EndThenEnd;PrintProcedureMain(s:Shortint);Vari,j,k:Integer;t,x:Longint;BeginFori:=1toNDoBegin僅含一堆石子的序列不存在合并Listi,1.c:=0;Listi,1.d:=0End;ForForj:=2toNDo順推含2堆,含3堆,含N堆石子的各子序列的合并方案Fori:=1toNDoBegin當(dāng)前考慮從第i堆數(shù)起,順時(shí)針數(shù)j堆的子序列Ifs=1ThenListi,j.c:=合并i,j子序列的得分和初始化MaxlongintEl

19、seListi,j.c:=0;t:=Sum件i,j;最后一次合并的得分為i,j子序列的石子總數(shù)Fork:=1toj-1DoBegin子序列1的石子堆數(shù)依次考慮1堆,j-1堆x:=(i+k-1)ModN+1;求子序列2首堆序號(hào)If(s=1)And(Listi,k.c+Listx,j-k.c+t<Listi,j.c)Or(s=2)And(Listi,k.c+Listx,j-k.c+t>Listi,j.c)若該合并方案為目前最佳,則記下ThenBeginListi,j.c:=Listi,k.c+Listx,j-k.c+t;Listi,j.d:=kEndThenEndForEnd;For在子序列1,N,2,N,N,N中選擇得分總和最小(或最大)的一個(gè)子序列k: