1207122113_胡文峰_实验三-1动态规划

算法设计与分析实验报告学号1207122113姓名胡文峰班级12软金1上课地点1-307教师王大寒上课时间2015/4/8实验四动态规划1.实验目的1.1．理解动态规划算法的主要设计思想；1.2．掌握用动态规划算法策略解决最小合并问题和资源分配问题。2.实验环境2.1Eclipse,C++2.2WindowXP3.实验内容1、石子合并问题，参考矩阵连乘的动态规划解法实现石子合并问题，并分析算法的时间复杂度。2、优化石子合并问题的动态规划算法，将算法复杂度从O(n3)降到O(n2)。4.教师批改意见签字：日期：成绩实验报告细表1实验题目1.1算法设计思想本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子：6346542如果使用贪心法求最小得分，应该是如下的合并步骤：第一次合并3465422,3合并得分是5第二次合并546545,4合并得分是9第三次合并96545,4合并得分是9第四次合并9699,6合并得分是15第五次合并15915,9合并得分是24总得分＝5＋9＋9＋15＋24＝62但是如果采用如下合并方法，却可以得到比上面得分更少的方法：第一次合并3465423,4合并得分是7第二次合并765427,6合并得分是13第三次合并135424,2合并得分是6第四次合并13565,6合并得分是11第五次合并131113,11合并得分是24总得分＝7＋13＋6＋11＋24＝61由此我们知道本题是不可以使用贪心法求解的，上例中第五次合并石子数分别为13和11的相邻两堆。这两堆石头分别由最初的第1，2，3堆（石头数分别为3，4，6）和第4，5，6堆（石头数分别为5，4，2）经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N－2次合并的得分总和最优。为了实现这一目标，我们将第１个序列又一分为二：第１、２堆构成子序列１，第３堆为子序列２。第一次合并子序列１中的两堆，得分７；第二次再将之与子序列２的一堆合并，得分13。显然对于第１个子序列来说，这样的合并方案是最优的。同样，我们将第２个子序列也一分为二；第４堆为子序列１，第５，６堆构成子序列２。第三次合并子序列２中的２堆，得分６；第四次再将之与子序列１中的一堆合并，得分13。显然对于第二个子序列来说，这样的合并方案也是最优的。由此得出一个结论──６堆石子经过这样的５次合并后，得分的总和最小。动态规划思路：阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N堆合并状态s：每一阶段中各个不同合并方法的石子合并总得分。决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案具体来说我们应该定义一个数组s[i,j]用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s[i,j]为合并的最优得分。对于上面的例子来说，初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因为一开始还没有合并，所以这些值应该全部为0。第二阶段：两两合并过程如下，其中sum(i,j)表示从i开始数j个数的和s[1,2]=s[1,1]+s[2,1]+sum(1,2)s[2,2]=s[2,1]+s[3,1]+sum(2,2)s[3,2]=s[3,1]+s[4,1]+sum(3,2)s[4,2]=s[4,1]+s[5,1]+sum(4,2)s[5,2]=s[5,1]+s[6,1]+sum(5,2)s[6,2]=s[6,1]+s[1,1]+sum(6,2)第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个为一组s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3)，取其最优s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3)，取其最优第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。以后第五阶段、第六阶段依次类推，最后在第六阶段中找出最优答案即可。由此得到算法框架如下：Forj←2tondo{枚举阶段，从两两合并开始计算}Fori←1tondo{计算当前阶段的n种不同状态的值}Fork←1toj-1do{枚举不同的分段方法}beginIfi+knthent←(i+k)modnelset←i+k{最后一个连第一个的情况处理}s[i,j]←最优{s[i,k]+s[t,j-k]+sum[1,3]}{sum[i,j]表示从i开始数j个数的和}end;1.2程序源码#includestdio.h#defineN100/**求合并过程中*最少合并堆数目**/intMatrixChain_min(intp[N],intn){//定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目//此处赋值为-1intm[N][N];for(intx=1;x=n;x++)for(intz=1;z=n;z++){m[x][z]=-1;}intmin=0;//当一个单独合并时，m[i][i]设为0，表示没有石子for(intg=1;g=n;g++)m[g][g]=0;//当相邻的两堆石子合并时，此时的m很容易可以看出是两者之和for(inti=1;i=n-1;i++){intj=i+1;m[i][j]=p[i]+p[j];}//当相邻的3堆以及到最后的n堆时，执行以下循环for(intr=3;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;//j总是距离ir-1的距离intsum=0;//当i到j堆石子合并时最后里面的石子数求和得sumfor(intb=i;b=j;b++)sum+=p[b];//此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+sum结果，这是其中一种可能，不一定是最优//要与下面的情况相比较，唉，太详细了m[i][j]=m[i+1][j]+sum;//除上面一种组合情况外的其他组合情况for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+sum;if(tm[i][j])m[i][j]=t;}}//最终得到最优解min=m[1][n];returnmin;}/**求合并过程中*最多合并堆数目**/intMatrixChain_max(intp[N],intn){intm[N][N];for(intx=1;x=n;x++)for(intz=1;z=n;z++){m[x][z]=-1;}intmax=0;//一个独自组合时for(intg=1;g=n;g++)m[g][g]=0;//两个两两组合时for(inti=1;i=n-1;i++){intj=i+1;m[i][j]=p[i]+p[j];}for(intr=3;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;intsum=0;for(intb=i;b=j;b++)sum+=p[b];m[i][j]=m[i+1][j]+sum;for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+sum;if(tm[i][j])m[i][j]=t;}}max=m[1][n];returnmax;}intmain(){intstone[N];intmin=0;intmax=0;intn;printf(实验3动态规划\n);printf(题目：石子合并问题\n);printf(姓名：胡文峰学号：1207122113\n);printf(输入：);scanf(%d,&n);for(inti=1;i=n;i++)scanf(%d,&stone[i]);min=MatrixChain_min(stone,n);max=MatrixChain_max(stone,n);//因为题目要求圆的原因，要把所有情况都要考虑到，总共有n种情况。for(intj=1;j=n-1;j++){intmin_cache=0;intmax_cache=0;intcache=stone[1];for(intk=2;k=n;k++){stone[k-1]=stone[k];}stone[n]=cache;min_cache=MatrixChain_min(stone,n);max_cache=MatrixChain_max(stone,n);if(min_cachemin)min=min_cache;if(max_cachemax)max=max_cache;}printf(输出:\n);printf(%d\n,min);printf(%d\n,max);return1;}1.3实验结论（结果验证）1.4心得体会算法思想只懂个大概，代码网络上找的，自己实现由点困难。