[计算机]石子合并问题报告

[计算机]石子合并问题 石子合并(动态规划)详细解题报告 2007-02-25 14:58 一, 在一个园形操场的四周摆放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堆,，第2堆、„„、第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){关闭输出文件} End.