轉帖
在一個圓形操場的四周擺放著n堆石子。現要將石子有次序地合并成一堆。規定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分。試設計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。 
 
 
假設有n堆石子需要合并,可以設計一個2*n-1個元素的數組來存儲每堆石子的個數。
分析最優解的結構：假設有石頭AiAi+1……Aj需要合并,簡記為A[i,j].如果設最后一次合并發生在Ak與Ak+1之間(i<=k<j),則最后一個合并的得分為Ai……Aj堆石頭的個數的總和記為totalValue(i,j).(不管你最后一次合并發生在哪個位置,totalValue(i,j)的值都是一樣的)因此總的得分等于A[i,k]的得分加上A[k+1,j]的得分再加上totalValue(i,j).
可以假設計算A[0,n-1]的一個最優次序所包含的計算子鏈A[0,k]和A[K+1,n-1]的次序也是最優的.
 證明:
 假設存在一個比計算A[0,k]的次序得分更少的次序,則用此次序來替換原來計算A[0,k]的次序,那么此時計算A[0,n-1]次序的得分就會比最優次序所得到的分數更少,這與假設相矛盾;同理可證明:計算A[0,n-1]的一個最優次序所包含的另一個計算子鏈A[k+1,n-1]的次序也是最優的!

綜上所述,此題滿足最優子結構性質,因此可以用動態規劃算法來求解.
建立遞歸關系
設m[i][j]表示A[i,j]的計算結果.
當i=j時,表示只有一堆石頭,不能合并,因此得分為零,所以m[i,j]=0;
當i<j時,可利用最優子結構性質來計算m[i][j],
m[i,j]=m[i,k]+m[k+1,j]+totalValue(i,j)(i<=k<j)

可用矩陣連乘的最優計算次序問題來求解這題.可選用自頂向下的備忘錄算法或是自底向上的動態規劃算法.

以下代碼使用動態規劃算法:

void MatrixChain(int *p,int n,int **m,int flag) //矩陣連乘算法
{
for(int i=0;i<n;i++)
m[i][i]=0;
for(int r=2;r<n;r++)
for(int i=0;i<n-r+1;i++)
{
int j=i+r-1;
int temp=totalValue(i,j,p);
m[i][j]=m[i+1][j]+temp;
for(int k=i+1;k<j;k++)
{
int t=m[i][k]+m[k+1][j]+temp;
if(!flag) //求最小得分
{
 if(t<m[i][j])
 m[i][j]=t;
}
else //求最大得分
if(t>m[i][j])
m[i][j]=t;
}
}
}
MatrixChain(inputNum,2*n-1,m,0); //計算最小得分
int resultMin=m[0][n-1];
for(i=1;i<=n-1;i++)
if(resultMin>m[i][n-1+i])
resultMin=m[i][n-1+i];

MatrixChain(inputNum,2*n-1,m,1); //計算最大得分
int resultMax=m[0][n-1];
for(i=1;i<=n-1;i++)
if(resultMax<m[i][n-1+i])
resultMax=m[i][n-1+i]; 
 
 
 

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/lyflower/archive/2008/03/05/2150239.aspx

一．試題
      在一個園形操場的四周擺放N堆石子（N≤100），現要將石子有次序地合并成一堆。規定
      每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數，記為該次合并的得分。
      編一程序，由文件讀入堆數N及每堆的石子數（≤２０），
      ①選擇一種合并石子的方案，使得做N－1次合并，得分的總和最小；
      ②選擇一種合并石子的方案，使得做N－1次合并，得分的總和最大。
      例如，所示的４堆石子，每堆石子數（從最上面的一堆數起，順時針數）依
      次為４５９４。則３次合并得分總和最小的方案：８＋１３＋２２＝４３
      得分最大的方案為：１４＋１８＋２２＝５４
      輸入數據：
      文件名由鍵盤輸入，該文件內容為：
      第一行為石子堆數N；
      第二行為每堆的石子數，每兩個數之間用一個空格符分隔。
      輸出數據：
      輸出文件名為output.txt
      從第1至第N行為得分最小的合并方案。第N＋1行是空行。從第N＋2行到第2N＋1行是得
      分最大合并方案。
      每種合并方案用N行表示，其中第i行（1≤i≤N）表示第i 次合并前各堆的石子數（依
      順時針次序輸出，哪一堆先輸出均可）。 要求將待合并的兩堆石子數以相應的負數表示，以便標識。

      輸入輸出范例：
      輸入文件內容：
      ４
      ４ ５９ ４
      輸出文件內容：
      －４ ５ ９ －４
      －８－５ ９
      －１３ －９
      ２２
      
      ４ －５ －９ ４
      ４ －１４ －４
      －４－１８
      ２２

      二．算法分析
      競賽中多數選手都不約而同地采用了盡可能逼近目標的貪心法來逐次合并：從最上面
      的一堆開始，沿順時針方向排成一個序列。 第一次選得分最小（最大）的相鄰兩堆合并，
      形成新的一堆；接下來，在N－1堆中選得分最小（最大）的相鄰兩堆合并……，依次類推，
      直至所有石子經N－1次合并后形成一堆。

      例如有６堆石子，每堆石子數（從最上面一堆數起，順時針數）依次為３ ４６ ５ ４ ２
      要求選擇一種合并石子的方案，使得做５次合并，得分的總和最小。
      按照貪心法，合并的過程如下：
      每次合并得分
      第一次合并 ３ ４ ６ ５ ４ ２ ->５
      第二次合并 ５ ４ ６ ５ ４    ->９
      第三次合并 ９ ６ ５ ４       ->９
      第四次合并 ９ ６ ９          ->１５
      第五次合并 １５ ９           ->２４
      24
      總得分＝５＋９＋９＋１５＋２４＝６２

      但是當我們仔細琢磨后，可得出另一個合并石子的方案：
      每次合并得分
      第一次合并 ３ ４ ６ ５ ４ ２  ->７
      第二次合并 ７ ６ ５ ４ ２     ->１３
      第三次合并 １３ ５ ４ ２      ->６
      第四次合并 １３ ５ ６         ->１１
      第五次合并 １３ １１          ->２４
      24
      總得分＝７＋６＋１１＋１３＋２４＝６１
      顯然，后者比貪心法得出的合并方案更優。 題目中的示例故意造成一個貪心法解題的
      假像，誘使讀者進入“陷阱”。為了幫助讀者從這個“陷阱”里走出來， 我們先來明確一個問題：

      １．最佳合并過程符合最佳原理
      使用貪心法至所以可能出錯，
      是因為每一次選擇得分最小（最大）的相鄰兩堆合并，不一定保證余下的合并過程能導致最優解。聰明的讀者馬上會想到一種理想的假設：如果N－1次合并的全局最優解包含了每一次合并的子問題的最優解，那么經這樣的N－1次合并后的得分總和必然是最優的。
      例如上例中第五次合并石子數分別為１３和１１的相鄰兩堆。
      這兩堆石頭分別由最初的第１，２，３堆（石頭數分別為３，４，６）和第４，５，６堆（石頭數分別為５，４，２）經４次合并后形成的。于是問題又歸結為如何使得這兩個子序列的N－2
      次合并的得分總和最優。為了實現這一目標，我們將第１個序列又一分為二：第１、２堆構成子序列１，
      第３堆為子序列２。第一次合并子序列１中的兩堆，得分７；
      第二次再將之與子序列２的一堆合并，得分１３。顯然對于第１個子序列來說，這樣的合并方案是最優的。同樣，我們將第２個子序列也一分為二；第４堆為子序列１，第５，６堆構成子序列２。第三次合并子序列２中的２堆，得分６；第四次再將之與子序列１中的一堆合并，得分１３。顯然對于第二個子序列來說，這樣的合并方案也是最優的。
      由此得出一個結論──６堆石子經
      過這樣的５次合并后，得分的總和最小。我們把每一次合并劃分為階段，當前階段中計算出的得分和作為狀態，
      如何在前一次合并的基礎上定義一個能使目前得分總和最大的合并方案作為一次決策。很顯然，某階段的狀態給定后，則以后各階段的決策不受這階段以前各段狀態的影響。
      這種無后效性的性質符最佳原理，因此可以用動態規劃的算法求解。

      ２．動態規劃的方向和初值的設定
      采用動態規劃求解的關鍵是確定所有石子堆子序列的最佳合并方案。 這些石子堆子序列包括：
      ｛第１堆、第２堆｝、｛第２堆、第３堆｝、……、｛第N堆、第１堆｝；
      ｛第１堆、第２堆、第３堆｝、｛第２堆、第３堆、第４堆｝、……、｛第N堆、第１堆、第２堆｝；……
      ｛第１堆、……、第N堆｝｛第１堆、……、第N堆、第１堆｝……｛第N堆、第１堆、……、第N－１堆｝

      為了便于運算，我們用〔i，j〕表示一個從第i堆數起，順時針數j堆時的子序列｛第i堆、第i＋１堆、……、第（i＋j－1）mod n堆｝
      它的最佳合并方案包括兩個信息：
      ①在該子序列的各堆石子合并成一堆的過程中，各次合并得分的總和；
      ②形成最佳得分和的子序列１和子序列２。由于兩個子序列是相鄰的， 因此只需記住子序列１的堆數；
      設
      f〔i，j〕──將子序列〔i，j〕中的j堆石子合并成一堆的最佳得分和；
      c〔i，j〕──將〔i，j〕一分為二，其中子序列１的堆數；
      （１≤i≤N，１≤j≤N）
      顯然，對每一堆石子來說，它的
      f〔i，１〕＝０
      c〔i，１〕＝０ （１≤i≤N）
      對于子序列〔i，j〕來說，若求最小得分總和，f〔i，j〕的初始值為∞； 若求最大得分總和，f〔i，j〕的初始值為０。（１≤i≤N，２≤j≤N）。
      動態規劃的方向是順推(即從上而下)。先考慮含二堆石子的N個子序列（各子序列分別從第１堆、第２堆、……、第N堆數起，順時針數２堆）的合并方案
      f〔１，２〕，f〔２，２〕，……，f〔N，２〕
      c〔１，２〕，c〔２，２〕，……，c〔N，２〕
      然后考慮含三堆石子的Ｎ個子序列（各子序列分別從第１堆、第２堆、……、第Ｎ堆數起，順時針數３堆）的合并方案
      f〔１，３〕，f〔２，３〕，……，f〔N，３〕
      c〔１，３〕，c〔２，３〕，……，c〔N，３〕
      ……
      依次類推，直至考慮了含N堆石子的N個子序列（各子序列分別從第１堆、第２堆、 ……、第N堆數起，順時針數N堆）的合并方案
      f〔１，N〕，f〔２，N〕，……，f〔N，N〕
      c〔１，N〕，c〔２，N〕，……，c〔N，N〕
      最后，在子序列〔１，N〕，〔２，N〕，……，〔N，N〕中，選擇得分總和（f值）最小（或最大）的一個子序列〔i，N〕（１≤i≤N），由此出發倒推合并過程。

      ３．動態規劃方程和倒推合并過程
      對子序列〔i，j〕最后一次合并，其得分為第i堆數起，順時針數j堆的石子總數t。被合并的兩堆石子是由子序列〔i，k〕和〔（i＋k－１）mod
      n＋１，j－k〕（１≤k≤j－１）經有限次合并形成的。為了求出最佳合并方案中的k值，我們定義一個動態規劃方程：
      當求最大得分總和時
      f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
      １≤k≤j－１
      c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
      （２≤ｊ≤ｎ，１≤ｉ≤ｎ）

      當求最小得分總和時
      f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝
      １≤k≤j－１
      c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
      （２≤ｊ≤ｎ，１≤ｉ≤ｎ）
      其中x＝（i＋k－１）modn＋１，即第i堆數起，順時針數k＋１堆的堆序號。

      例如對上面例子中的６(３ ４ ６ ５ ４ ２ )堆石子，按動態規劃方程順推最小得分和。 依次得出含二堆石子的６個子序列的合并方案
      f〔１，２〕＝７ f〔２，２〕＝１０ f〔３ ，２〕＝１１
      c〔１，２〕＝１ c〔２，２〕＝１ c〔３，２〕＝１
      f〔４，２〕＝９ f〔５，２〕＝６ f〔６，２〕＝５
      c〔４，２〕＝１ c〔５， ２〕＝１ c〔６，２〕＝１

      含三堆石子的６(３ ４ ６ ５ ４ ２ )個子序列的合并方案
      f〔１，３〕＝２０ f〔２，３〕＝２５ f〔３，３〕＝２４
      c〔１，３〕＝２ c〔２，３〕＝２ c〔３，３〕＝１
      f〔４，３〕＝１７ f〔５，３〕＝１４ f〔６，３〕＝１４
      c〔４，３〕＝１ c〔５，３〕＝１ c〔６，３〕＝２

      含四堆石子的６(３ ４ ６ ５ ４ ２ )個子序列的合并方案
      f〔１，４〕＝３６ f〔２，４〕＝３８ f〔３，４〕＝３４
      c〔１，４〕＝２ c〔２，４〕＝２ c〔３，４〕＝１
      f〔４，４〕＝２８ f〔５，４〕＝２６ f〔６，４〕＝２９
      c〔４，４〕＝１ c〔５，４〕＝２ c〔６，４〕＝３

      含五堆石子的６(３ ４ ６ ５ ４ ２ )個子序列的合并方案
      f〔１，５〕＝５１ f〔２，５〕＝４８ f〔３，５〕＝４５
      c〔１，５〕＝３ c〔２，５〕＝２ c〔３，５〕＝２
      f〔４，５〕＝４１ f〔５，５〕＝４３ f〔６，５〕＝４５
      c〔４，５〕＝２ c〔５，５〕＝３ c〔６，５〕＝３

      含六堆石子的６(３ ４ ６ ５ ４ ２ )個子序列的合并方案
      f〔１，６〕＝６１ f〔２，６〕＝６２ f〔３，６〕＝６１
      c〔１，６〕＝３ c〔２，６〕＝２ c〔３，６〕＝２
      f〔４，６〕＝６１ f〔５，６〕＝６１ f〔６，６〕＝６２
      c〔４，６〕＝３ c〔５，６〕＝４ c〔６，６〕＝３

      f〔１，６〕是f〔１，６〕，ｆ〔２，６〕，……f〔６，６〕中的最小值，表明最小得分和是由序列〔１，６〕經５次合并得出的。我們從這個序列出發，
      按下述方法倒推合并過程：
      由c〔１，６〕＝３可知，第５次合并的兩堆石子分別由子序列〔１，３〕和子序列〔４，3〕經４次合并后得出。其中c〔１，３〕＝２可知由子序列〔１，３〕合并成的一堆石子是由子序列〔１，２〕和第三堆合并而來的。而c〔１，２〕＝１，以表明了子序列〔１，２〕的合并方案是第１堆合并第２堆。
      由此倒推回去，得出第１，第２次合并的方案，每次合并得分
      第一次合并 ３ ４ ６…… 　　　->７
      第二次合并 ７ ６……          ->１３
      １３……
      子序列〔１，３〕經２次合并后合并成１堆， ２次合并的得分和＝７＋１３＝２０。
      ｃ〔４，３〕＝１，可知由子序列〔４，３〕合并成的一堆石子是由第４堆和子序列〔５，
      ２〕合并而來的。而c〔５，２〕＝１，又表明了子序列〔５，２〕的合并方案是第５堆合并第６堆。由此倒推回去，得出第３、第４次合并的方案
      每次合并得分：
       第三次合并 ……５４ ２     ->６
      第四次合并 ……５ ６        ->１１
      ……１１
      子序列〔４，３〕經２次合并后合并成１堆，２次合并的得分和＝６＋１１＝１７。
      第五次合并是將最后兩堆合并成１堆，該次合并的得分為２４。
      顯然，上述５次合并的得分總和為最小
      ２０＋１７＋２４＝６１

      上述倒推過程，可由一個print（〔子序列〕）的遞歸算法描述
      procedure print （〔i，ｊ〕）
      begin
      if ｊ〈〉１ then ｛繼續倒推合并過程
      begin
      print（〔i，c〔i，j〕〕；｛倒推子序列１的合并過程｝
      print（〔i＋c〔i，j〕－１〕mod n＋１，j－c〔i，j〕）
      ｛倒推子序列２的合并過程｝
      for K：＝１ to N do｛輸出當前被合并的兩堆石子｝
      if （第K堆石子未從圈內去除）
      then begin
      if（K＝i）or（K＝X）then置第K堆石子待合并標志
      else第K堆石子未被合并；
      end；｛then｝
      第i堆石子數←第i堆石子數＋第X堆石子數；
      將第X堆石子從圈內去除；
      end；｛then｝
      end；｛print｝
      例如，調用print（〔１，６〕）后的結果如下：
                           print（〔１，６〕）⑤
                                ┌──────┴──────┐
                     print（〔１，３〕）②               print（〔４，３〕）④
                ┌─────┴─────┐               ┌─────┴─────┐
          print(〔１，２〕)① print(〔3，1〕)     print(〔4，1〕) print(〔５，２〕)③
       ┌──────┴──────┐                         ┌──────┴──────┐             
      print（〔1,1〕）        print（〔2,1〕）               print（〔5,1〕）        
      print（〔6,1〕）
      （圖6.2-5）
      其中回溯至
      ① 顯示 ３ ４６ ５ ４
      ② 顯示 ７ ６５ ４ ２
      ③ 顯示 １３ ５４ ２
      ④ 顯示 １３５ ６
      ⑤ 顯示 １３ １１
      注:調用print過程后，應顯示６堆石子的總數作為第５次合并的得分。

      Program Stones;
      Type
      Node = Record{當前序列的合并方案}
      c : Longint;{得分和}
      d : Byte{子序列1的堆數}
      End;
      SumType = Array [1..100,1..100] of Longint;
      {sumtype[i,j]-子序列[i,j]的石子總數}
      Var
      List : Array [1..100,1..100] of Node;
      {list[i,j]-子序列[i,j]的合并方案}
      Date, Dt : Array [1..100] of Integer;
      {Date[i]-第i堆石子數,Dt-暫存Date}
      Sum : ^SumType;{sum^[i,j]-指向子序列[i,j]的石子總數的指針}
      F : Text;{文件變量}
      Fn : String;{文件名串}
      N, i, j : Integer;{N-石子堆數,i,j-循環變量}

      Procedure Print(i, j : Byte);{遞歸打印子序列[i,j]的合并過程}
      Var
      k, x : Shortint;{k-循環變量;x-子序列2中首堆石子的序號}
      Begin
      If j <> 1 Then Begin{繼續倒推合并過程}
        Print(i, List[i,j].d);{倒推子序列1的合并過程}
        x := (i + List[i, j].d - 1) Mod N + 1;{求子序列2中首堆石子的序號}
        Print(x, j - List[i, j].d);{倒推子序列2的合并過程}
        For k := 1 to N Do{輸出當前合并第i堆,第x堆石子的方案}
          If Date[k] > 0 Then Begin
             If (i= k)or(x=k)Then Write(F, - Date[k], ' ')
             Else Write(F, Date[k], ' ')
          End; { Then }
        Writeln(F);{輸出換行符}
        Date[i] := Date[i] + Date[x];{原第i堆和第x堆合并成第ｉ堆}
        Date[x] := - Date[x]{將原第x堆從圈內去除}
        End { Then }
      End; { Print }

      Procedure Main(s : Shortint);
      Var
        i, j, k : Integer;
        t, x : Longint;
      Begin
        For i := 1 to N Do Begin{僅含一堆石子的序列不存在合并}
          List[i, 1].c := 0;
          List[i, 1].d := 0
        End; {For}
        For j := 2 to N Do{順推含2堆,含3堆……含N堆石子的各子序列的合并方案}
          For i := 1 to N Do Begin{當前考慮從第i堆數起,順時針數j堆的子序列}
            If s = 1 Then List[i, j].c := Maxlongint{合并[i,j]子序列的得分和初始化}
             Else List[i, j].c := 0;
            t := Sum^[i, j];{最后一次合并的得分為[i,j]子序列的石子總數}
            For k := 1 to j - 1 Do Begin{子序列1的石子堆數依次考慮1堆……j-1堆}
              x := (i + k - 1) Mod N + 1;{求子序列2首堆序號}
              If (s=1) And (List[i,k].c + List[x,j-k].c+t < List[i, j].c)
      Or (s=2) And (List[i,k].c + List[x,j-k].c+t > List[i, j].c)
      { 若該合并方案為目前最佳,則記下}
              Then Begin
                List[i, j].c := List[i, k].c + List[x, j - k].c + t;
                List[i, j].d := k
              End { Then }
            End { For }
        End; { For }
      {在子序列[1,N],[2,N],……,[N, N]中選擇得分總和最小(或最大)的一個子序列}
        k := 1; x := List[1, N].c;
        For i := 2 to N Do
          If (s = 1) And (List[i, N].c < x) Or (s = 2) And
      (List[i, N].c > x) Then Begin
             k := i; x := List[i, N].c
          End; { Then }
        Print(k, N);{由此出發,倒推合并過程}
        Writeln(F, Sum^[1, N]);{輸出最后一次將石子合并成一堆的石子總數}
        Writeln(F);
        Writeln(list[k, N].c)
      End; { Main }

      Begin
        Write('File name = ');{輸入文件名串}
        Readln(Fn);
        Assign(F, Fn);{該文件名串與文件變量連接}
        Reset(F);{文件讀準備}
        Readln(F, N);{讀入石子堆數}
        For i := 1 to N Do Read(F, Date[i]);{讀入每堆石子數}
        New(Sum);{求每一個子序列的石子數sum}
        For i := 1 to N Do Sum^[i, 1] := Date[i];
        For j := 2 to N Do
          For i := 1 to N Do
            Sum^[i, j] := Date[i] + Sum^[i Mod N + 1, j - 1];
        Dt := Date;{暫存合并前的各堆石子,結構相同的變量可相互賦值}
        Close(F);{關閉輸入文件}
        Assign(F, 'OUTPUT.TXT');{文件變量與輸出文件名串連接}
        Rewrite(F);{文件寫準備}
        Main(1);{求得分和最小的合并方案}
        Date := Dt;{恢復合并前的各堆石子}
        Main(2);{求得分和最大的合并方案}
        Close(F){關閉輸出文件}

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/lyflower/archive/2008/03/05/2150251.aspx