《石子合并问题报告》由会员分享，可在线阅读，更多相关《石子合并问题报告（23页珍藏版）》请在金锄头文库上搜索。
1、每次只能1行是得顺时针次序输入输出范石子合并（动态规划）详细解题报告007-02-2514:58试题在一个园形操场的四周摆放N堆石子（NW100）,现要将石子有次序地合并成一堆。规定选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。编一程序，由文件读入堆数N及每堆的石子数（20）,选择一种合并石子的方案，使得做N1次合并，得分的总和最小；选择一种合并石子的方案，使得做N1次合并，得分的总和最大。例如，所示的4堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依次为4594。则3次合并得分总和最小的方案：8+13+22=43得分最大的方案为：14+18+22=54输入数据：文
2、件名由键盘输入，该文件内容为：第一行为石子堆数N；第二行为每堆的石子数，每两个数之间用一个空格符分隔。输出数据：输出文件名为output.txt从第1至第N行为得分最小的合并方案。第N+1行是空行。从第N+2行到第2N+分最大合并方案。每种合并方案用N行表示，其中第i行（1i5第二次合并54654-9第三次合并9654-9第四次合并969?15第五次合并159?2424总得分=5+9+9+15+24=62每次合并得分第一次合并346542-7第二次合并76542?13第三次合并13542-6F1356-111311-24但是当我们仔细琢磨后，可得出另一个合并石子的方总得分=7+6+11+13+
3、24=61显然，后者比贪心法得出的合并方案更优。题目中的示例故意造成一个贪心法解题的假像，诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来，我们先来明确一个问题：1最佳合并过程符合最佳原理使用贪心法至所以可能出错，是因为每一次选择得分最小（最大）的相邻两堆合并，不一定保证余下的合并过程能导致最优解。聪明的读者马上会想到一种理想的假设：如果N1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N1次合并后的得分总和必然是最优的。例如上例中第五次合并石子数分别为13和11的相邻两堆。这两堆石头分别由最初的第1,2,3堆（石头数分别为3,4,6）和第4,5,6堆（石头数分别为5
4、,4,2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N2次合并的得分总和最优。为了实现这一目标,我们将第1个序列又一分为二：第1、2堆构成子序列1,第3堆为子序列2。第一次合并子序列1中的两堆,得分7；第二次再将之与子序列2的一堆合并,得分13。显然对于第1个子序列来说,这样的合并方案是最优的。同样,我们将第2个子序列也一分为二；第4堆为子序列1,第5,6堆构成子序列2。第三次合并子序列2中的2堆,得分6；第四次再将之与子序列1中的一堆合并,得分13。显然对于第二个子序列来说,这样的合并方案也是最优的。由此得出一个结论一一6堆石子经过这样的5次合并后,得分的总和最小。我们把每一
5、次合并划分为阶段,当前阶段中计算出的得分和作为状态,如何在前一次合并的基础上定义一个能使目前得分总和最大的合并方案作为一次决策。很显然,某阶段的状态给定后,则以后各阶段的决策不受这阶段以前各段状态的影响。这种无后效性的性质符最佳原理,因此可以用动态规划的算法求解第N堆、第1堆、第2堆第N堆、第1堆、，、第N1堆它的最佳合并N)动态规划的方,、第N堆数起，顺时针数22.动态规划的方向和初值的设定这些石子堆子序列包括：采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。第1堆、第2堆、第2堆、第3堆、，、第N堆、第1堆第1堆、第2堆、第3堆、第2堆、第3堆、第4堆、第1堆、,、第N堆第2堆
6、、,、第N堆、第1堆为了便于运算，我们用i,j表示一个从第i堆数起，顺时针数j堆时的子序列第i堆、第i+1堆、，,、第(i+j1)modn堆方案包括两个信息： 在该子序列的各堆石子合并成一堆的过程中，各次合并得分的总和；形成最佳得分和的子序列1和子序列2。由于两个子序列是相邻的，因此只需记住子序列1的堆数；设fi,j将子序列i,j丨中的j堆石子合并成一堆的最佳得分和；ci,j一一将i,jI一分为二，其中子序列1的堆数；(1iN,1jN)显然，对每一堆石子来说，它的fi,1=0ci,1=0(1iN)对于子序列i,j丨来说，若求最小得分总和，fi,j的初始值为若求最大得分总和，fi,j的初始值为0
7、。(1wiN,2j向是顺推(即从上而下)。先考虑含二堆石子的N个子序列(各子序列分别从第1堆、第2堆、堆）的合并方案f1,2，f2,2，,fN,2c1,2，c2,2，”,cN,2、第N堆数起，顺时针数3堆）的合并方案,，、第N堆数起，顺时针数N堆）的合并方案然后考虑含三堆石子的N个子序列（各子序列分别从第1堆、第2堆、f1，3，f2，3，fN,3c1，3，c2，3，,，cN,3依次类推，直至考虑了含N堆石子的N个子序列（各子序列分别从第1堆、第2堆、fNfNc最2,i后，出发倒推合并过程。3.动态规划方程和倒推合并过程对子序列i，j最后一次合并，其得分为第i堆数起，顺时针数j堆的石子总数t。被
8、合并的两堆石子是由子序列i，k和（i+k-1）modn+1,j-k（1kj1）经有限次合并形成的。为了求出最佳合并方案中的k值，我们定义一个动态规划方程：当求最大得分总和时fi，j=maxfi，k+fx，j-k+tII.厂、CLI,Jj=kIfLI,Jj(2WjWn,1WiWn)=fCi?k+fx，j-k+t当求最小得分总和时fi,j=minfi,k+fx,jk+t1k7第二次合并76,-1313,子序列1,3丨经2次合并后合并成1堆，2次合并的得分和=7+13=20。c4,3=1,可知由子序列4,3合并成的一堆石子是由第4堆和子序列5,2合并而来的。而c5,2=1,又表明了子序列5,2丨的合
9、并方案是第5堆合并第6堆。由此倒推回去，得出第3、第4次合并的方案每次合并得分：第三次合并,542-6第四次合并,56-11,11子序列4,3经2次合并后合并成1堆,2次合并的得分和=6+11=17。第五次合并是将最后两堆合并成1堆,该次合并的得分为24。显然,上述5次合并的得分总和为最小20+17+24=61上述倒推过程,可由一个print（子序列）的递归算法描述procedureprint（i,j）beginifj1then继续倒推合并过程beginprint（i,ci,j；倒推子序列1的合并过程print（i+ci,j1modn+1,jci,j）倒推子序列2的合并过程forK:=1toNdo输出当前被合并的两堆石子if（第K堆石子未从圈内去除）thenbeginif（K=i）or（K=X）then置第K堆石子待合并标志else第K堆石子未被合并；end;then第i堆石子数?第i堆石子数+第X堆石子数；将第X堆石子从圈内去除；end;thenend;print例如，调用print（Cl,6）后的结果如下：print（1,6）printprintprint（
