文档介绍：动态规划石子合并
第一页，共16页
信工2013020441
问题描述
在一个圆形操场的四周摆放着n 堆石子,现要将石子有次序地合并成一堆。
规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
第二页，共16页
此问题的三个版本
任意版：有N堆石子，现要将石子有序的合并成一堆，每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。
(贪心算法，哈夫曼编码问题)
直线版：在一条直线上摆着N堆石子，其余条件不变。
圆形版：石子是排成圆形，其余条件不变。
第三页，共16页
问题初步分析
如果N－1次合并的全局最优解包含了每一次合并的子问题的最优解，那么经这样的N－1次合并后的得分总和必然是最优的。
此我们需要通过动态规划算法来求出最优解。
信工2013020441
第四页，共16页
信工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堆时......
第五页，共16页
动态规划通项
通项式
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，再加上两大堆合并的得分。
第六页，共16页
部分关键代码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];
}
第七页，共16页
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;
}
}
//最终得到最优解