石子合并问题

一．试题

      在一个园形操场的四周摆放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){关闭输出文件}