获取内容资料
综合学习

石子合并贪心算法

此问题的三个版本 任意版:有N堆石子,现要将石子有序的合并成一堆,每次只能移动任意的2堆石子合并,合并花费为将的一堆石子的数量。 (贪心算法,哈夫曼编码问题) 直线版:在一条直线上摆着N堆石子,其余条件不变。 圆形版:石子是排成圆形,其余条件不变。 问题初步分析 如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。 此我们需要通过动态规划算法来求出最优解。 动态规划通项 通项式 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,再加上两大堆合并的得分。 部分关键代码1 int MatrixChain_min(int p[N],int n) { //定义二维数组m[i][j]来记录i到j的合并过成中最少石子数目 //此处赋值为-1 int m[N][N];//初始化 for(int x=1;x =n;x++) for(int z=1;z =n;z++) { m[x][z]=-1; } int min=0; for(int g = 1;g =n;g++) m[g][g]=0;//主对角线 for(int i=1;i =n-1;i++) { int j=i+1; m[i][j]=p[i]+p[j]; } for(int r=3; r =n;r++) for(int i=1;i =n-r+1;i++) { int j = i+r-1; int sum=0; for(int b=i;b =j;b++)//最后一次合并的等分 sum+=p[b]; m[i][j] = m[i+1][j]+sum;//其中一种情况 //除上面一种组合情况外的其他组合情况 for(int k=i+1;k j;k++) { int t=m[i][k]+m[k+1][j]+sum; if(t m[i][j]) m[i][j] = t; } } //最终得到最优解 min=m[1][n]; return min; } 部分关键代码2 int main{ int stone[N]; ··· min= MatrixChain_min(stone,n); max= MatrixChain_max(stone,n); //将前面简化的问题重新考虑进来,将圆转化为n个线性序列 for(int j=1;j =n-1;j++) { int min_cache=0; int max_cache=0; int cache= stone[1]; for(int k=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) max=max_cache; } ··· } 程序运行结果 复杂度分析 线性时为O(n^2),环形时为O(n^3) DP优化 重构DP 优化方案1 DP优化 GarsiaWachs算法可以把时间复杂度压缩到O(nlogn) 《The Art of Computer Programming》第3卷6.2.2节 概要:设一个序列是A[0..n-1],每次寻找最小的一个满足A[k-1] =A[k+1]的k,(方便起见设A[-1]和A[n]等于正无穷大) 那么我们就把A[k]与A[k-1]合并,之后找最大的一个满足A[j] A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。 基本思想是通过树的最优性得到一个节点间深度的约束,之后证明操作一次之后的解可以和原来的解一一对应,并保证节点移动之后他所在的深度不会改变 有此定理保证,如此操作后问题的答案不会改变。 一个例子 A[-1] 186 64 35 32 103 A[n] 因为35 103,所以最小的k是3,我们先把35和32删除,得到他们的和67,并向前寻找一个第一个超过67的数,把67插入到他后面 186 67 64 103 因为67 103,所以k=2,67和64被删除了,和131应当放在186后 186 131 103 同上述操作,现在k=2(别忘了,还有A[-1]和A[n]等于正无穷大) 234 186 420 最后的答案就是各次合并的重量之和 420+234+131+67=852。 优化方案2 重构DP 以(i,j)表示一个从第i堆数起,顺时针数j堆时的子序列 (双参数DP,O(n^2)) 最佳合并方案包括两个信息: ①在该子序列的各堆石子合并成一堆的过程中,各次合并得分的总和 ②形成最佳得分和的子序列1和子序列2。由于两个子序列是相邻的, 因此只需记住子序列1的堆数 设: f(i,j)──将子序列(i,j)中的j堆石子合并成一堆的最佳得分和 c(i,j)──将(i,j)一分为二,其中子序列1的堆数 (1≤i≤N,1≤j≤N) f〔i,1〕=0 c〔i,1〕=0 (1≤i≤N) f〔1,2〕,f〔2,2〕,……,f〔N,2〕(sum(i,i+1)) c〔1,2〕,c〔2,2〕,……,c〔N,2〕 (1) …… f〔1,N〕,f〔2,N〕,……,f〔N,N〕 c〔1,N〕,c〔2,N〕,……,c〔N,N〕 f〔i,j〕=min{f〔i,k〕+f〔x,j-k〕+sum} 1≤k≤j-1 c〔i,j〕=k│ f〔i,j〕=f〔i,k〕+f〔x,j-k〕+sum (2≤j≤n,1≤i≤n) 其中x=(i+k-1)mod n +1,即第i堆数起,顺时针数 k+1堆的堆序号 动态规划思想:石子合并问题 信工2013020441 问题描述 在一个圆形操场的四周摆放着n 堆石子,现要将石子有次序地合并成一堆。 规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 信工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堆时……

 下载文档  收藏  赏

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注