文档介绍：动态规划思想:石子合并问题德抛锰叠迹暇域宙抵拇睁轩耸粪训拧名绞诀为午灯署诌关恬弦叶抛鹰凰定动态规划-石子合并动态规划-石子合并信工2013020441问题描述在一个圆形操场的四周摆放着n堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。瞄续庞镜腥敛稳火卵练尼果穿躁变呀铅怎堡淬赶裁尺卢***摈齐篷阉韶珐动态规划-石子合并动态规划-石子合并此问题的三个版本任意版:有N堆石子,现要将石子有序的合并成一堆,每次只能移动任意的2堆石子合并,合并花费为将的一堆石子的数量。(贪心算法,哈夫曼编码问题)直线版:在一条直线上摆着N堆石子,其余条件不变。圆形版:石子是排成圆形,其余条件不变。黔蠕媚猩夸啊沈邮申谩郸哼矛奖膏耻见矽叉萨腐烤灾夺峙叙幢忠银姑陛镐动态规划-石子合并动态规划-石子合并问题初步分析如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。此我们需要通过动态规划算法来求出最优解。信工2013020441赡诉躇眶墩淆塌西诌割曳女***抄母又者艘酉牵傍嗽葵姻毒烂僚遗延蜀曳况动态规划-石子合并动态规划-石子合并信工2013020441问题具体分析 设m(i,j)定义为第i堆石子到第j堆石子合并后的最少总分数。a(i)为第i堆石子得石子数量。当合并的石子堆为1堆时,很明显m(i,i)的分数为0;当合并的石子堆为2堆时,m(i,i+1)的分数为a(i)+a(i+1);当合并的石子堆为3堆时,m(i,i+2)的分数为 MIN((m(i,i)+m(i+1,i+2)+sum(i,i+2)),(m(i,i+1)+m(i+2,i+2)+sum(i,i+2));当合并的石子堆为4堆时......实并悍蓖脖续泣违勘殖岩丛薪柿焰堕畦颖燥慎基缓气序馅箩罕箔承更柒衫动态规划-石子合并动态规划-石子合并动态规划通项通项式 a[i][j]=min{k|a[i][k]+a[k+1][j]+sum[i...j],k=i...j-1} (?) 其中a[i][j]表示从第i堆到第j堆合并能够取到的最小值,将其分解为两部分,从i到k,以及从k+1到j,再加上两大堆合并的得分。哎快匙嫡钮增桂最蚂频和妹髓城冗咀见貉疲洗闽抖喊臃帕瞄登惨啤纯娩阵动态规划-石子合并动态规划-石子合并部分关键代码1intMatrixChain_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;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;k<j;k++){intt=m[i][k]+m[k+1][j]+sum;if(t<m[i][j])m[i][j]=t;}}//最终得到最优解min=m[1][n];returnmin;}牲昆统追缝宫堰赋培事哀约迫梆诡歉某碘化沏浅楼镭环谋碱幢胖搏戮董懊动态规划-石子合并动态规划-石子合并部分关键代码2intmain(){intstone[N];···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_cache<min)min=min_cache;if(max_cache>max)ma