石子合并问题报告

石子合并(动态规划)详细解题报告2007-02-25 14:58一试题 在一个园形操场的四周摆放N堆石子（N100），现要将石子有次序地合并成一堆。规定 每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 编一程序，由文件读入堆数N及每堆的石子数（）， 选择一种合并石子的方案，使得做N1次合并，得分的总和最小； 选择一种合并石子的方案，使得做N1次合并，得分的总和最大。 例如，所示的堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依 次为。则次合并得分总和最小的方案： 得分最大的方案为： 输入数据： 文件名由键盘输入，该文件内容为： 第一行为石子堆数N； 第二行为每堆的石子数，每两个数之间用一个空格符分隔。 输出数据： 输出文件名为output.txt 从第1至第N行为得分最小的合并方案。第N1行是空行。从第N2行到第2N1行是得 分最大合并方案。 每种合并方案用N行表示，其中第i行（1iN）表示第i 次合并前各堆的石子数（依 顺时针次序输出，哪一堆先输出均可）。 要求将待合并的两堆石子数以相应的负数表示，以便标识。 输入输出范例： 输入文件内容： 输出文件内容： 二算法分析 竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并：从最上面 的一堆开始，沿顺时针方向排成一个序列。 第一次选得分最小（最大）的相邻两堆合并， 形成新的一堆；接下来，在N1堆中选得分最小（最大）的相邻两堆合并，依次类推， 直至所有石子经N1次合并后形成一堆。 例如有堆石子，每堆石子数（从最上面一堆数起，顺时针数）依次为 要求选择一种合并石子的方案，使得做次合并，得分的总和最小。 按照贪心法，合并的过程如下： 每次合并得分 第一次合并 - 第二次合并 - 第三次合并 - 第四次合并 - 第五次合并 - 24 总得分 但是当我们仔细琢磨后，可得出另一个合并石子的方案： 每次合并得分 第一次合并 - 第二次合并 - 第三次合并 - 第四次合并 - 第五次合并 - 24 总得分 显然，后者比贪心法得出的合并方案更优。 题目中的示例故意造成一个贪心法解题的 假像，诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来， 我们先来明确一个问题： 最佳合并过程符合最佳原理 使用贪心法至所以可能出错， 是因为每一次选择得分最小（最大）的相邻两堆合并，不一定保证余下的合并过程能导致最优解。聪明的读者马上会想到一种理想的假设：如果N1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N1次合并后的得分总和必然是最优的。 例如上例中第五次合并石子数分别为和的相邻两堆。 这两堆石头分别由最初的第，堆（石头数分别为，）和第，堆（石头数分别为，）经次合并后形成的。于是问题又归结为如何使得这两个子序列的N2 次合并的得分总和最优。为了实现这一目标，我们将第个序列又一分为二：第、堆构成子序列， 第堆为子序列。第一次合并子序列中的两堆，得分； 第二次再将之与子序列的一堆合并，得分。显然对于第个子序列来说，这样的合并方案是最优的。同样，我们将第个子序列也一分为二；第堆为子序列，第，堆构成子序列。第三次合并子序列中的堆，得分；第四次再将之与子序列中的一堆合并，得分。显然对于第二个子序列来说，这样的合并方案也是最优的。 由此得出一个结论堆石子经 过这样的次合并后，得分的总和最小。我们把每一次合并划分为阶段，当前阶段中计算出的得分和作为状态， 如何在前一次合并的基础上定义一个能使目前得分总和最大的合并方案作为一次决策。很显然，某阶段的状态给定后，则以后各阶段的决策不受这阶段以前各段状态的影响。 这种无后效性的性质符最佳原理，因此可以用动态规划的算法求解。 动态规划的方向和初值的设定 采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。 这些石子堆子序列包括： 第堆、第堆、第堆、第堆、第N堆、第堆； 第堆、第堆、第堆、第堆、第堆、第堆、第N堆、第堆、第堆； 第堆、第N堆第2堆、第N堆、第堆第N堆、第堆、第N堆 为了便于运算，我们用i，j表示一个从第i堆数起，顺时针数j堆时的子序列第i堆、第i堆、第（ij1）mod n堆 它的最佳合并方案包括两个信息： 在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和； 形成最佳得分和的子序列和子序列。由于两个子序列是相邻的， 因此只需记住子序列的堆数； 设 fi，j将子序列i，j中的j堆石子合并成一堆的最佳得分和； ci，j将i，j一分为二，其中子序列的堆数； （iN，jN） 显然，对每一堆石子来说，它的 fi， ci， （iN） 对于子序列i，j来说，若求最小得分总和，fi，j的初始值为； 若求最大得分总和，fi，j的初始值为。（iN，jN）。 动态规划的方向是顺推(即从上而下)。先考虑含二堆石子的N个子序列（各子序列分别从第堆、第堆、第N堆数起，顺时针数堆）的合并方案 f，f，fN， c，c，cN， 然后考虑含三堆石子的个子序列（各子序列分别从第堆、第堆、第堆数起，顺时针数堆）的合并方案 f，f，fN， c，c，cN， 依次类推，直至考虑了含N堆石子的N个子序列（各子序列分别从第堆、第堆、 、第N堆数起，顺时针数N堆）的合并方案 f，N，f，N，fN，N c，N，c，N，cN，N 最后，在子序列，N，N，N，N中，选择得分总和（f值）最小（或最大）的一个子序列i，N（iN），由此出发倒推合并过程。 动态规划方程和倒推合并过程 对子序列i，j最后一次合并，其得分为第i堆数起，顺时针数j堆的石子总数t。被合并的两堆石子是由子序列i，k和（ik）mod n，jk（kj）经有限次合并形成的。为了求出最佳合并方案中的k值，我们定义一个动态规划方程： 当求最大得分总和时 fi，jmaxfi，kfx，j-kt kj ci，jk fi，jfi，kfx，j-kt （，） 当求最小得分总和时 fi，jminfi，kfx，jkt kj ci，jk fi，jfi，kfx，j-kt （，） 其中x（ik）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，ci，j；倒推子序列的合并过程 print（ici，jmod n，jci，j） 倒推子序列的合并过程 for K： to N do输出当前被合并的两堆石子 if （第K堆石子未从圈内去除） then begin if（Ki）or（KX）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; sumtypei,j-子序列i,j的石子总数 Var List : Array 1.100,1.100 of Node; listi,j-子序列i,j的合并方案 Date, Dt : Array 1.100 of Integer; Datei-第i堆石子数,Dt-暂存Date Sum : SumType;sumi,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, Listi,j.d);倒推子序列1的合并过程 x := (i + Listi, j.d - 1) Mod N + 1;求子序列2中首堆石子的序号 Print(x, j - Listi, j.d);倒推子序列2的合并过程 For k := 1 to N Do输出当前合并第i堆,第x堆石子的方案 If Datek 0 Then Begin If (i= k)or(x=k)Then Write(F, - Datek, ) Else Write(F, Datek, ) End; Then Writeln(F);输出换行符 Datei := Datei + Datex;原第i堆和第x堆合并成第堆 Datex := - Datex将原第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仅含一堆石子的序列不存在合并 Listi, 1.c := 0; Listi, 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 Listi, j.c := Maxlongint合并i,j子序列的得分和初始化 Else Listi, j.c := 0; t := Sumi, 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 (Listi,k.c + Listx,j-k.c+t Listi, j.c) 若该合并方案为目前最佳,则记下 Then Begin Listi, j.c := Listi, k.c + Listx, j - k.c + t; Listi, j.d := k End Then End For End; For 在子序列1,N,2,N,N, N中选择得分总和最小(或最大)的一个子序列 k := 1; x := List1, N.c; For i := 2 to N Do If (s = 1) And (Listi, N.c x) Then Begin k := i; x := Listi, N.c End; Then Print(k, N);由此出发,倒推合并过程 Writeln(F, Sum1, N);输出最后一次将石子合并成一堆的石子总数 Writeln(F); Writeln(listk, 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, Datei);读入每堆石子数 New(Sum);求每一个子序列的石子数sum For i :=