问题描述：
在一个园形操场的四周摆放N堆石子（N≤100），现要将石子有次序地合并成一堆。规定
每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
编一程序，由文件读入堆数N及每堆的石子数（≤２０），
①选择一种合并石子的方案，使得做N－1次合并，得分的总和最小；
②选择一种合并石子的方案，使得做N－1次合并，得分的总和最大。
例如，所示的４堆石子，每堆石子数（从最上面的一堆数起，顺时针数）依
次为４５９４。则３次合并得分总和最小的方案：８＋１３＋２２＝４３
得分最大的方案为：１４＋１８＋２２＝５４
该问题应该用动态规划算法才能得到最优解，而贪心算法得不到最优解。
而动态规划算法的基本要素是：最优子结构和重叠子问题
针对该问题，我们用f(i,j)表示从第i堆石子数起，顺时针数j堆石子的得分，则它的动态规划方程为
当求最大得分总和时
f〔i，j〕＝max｛f〔i，k〕＋f〔x，j-k〕＋t｝
１≤k≤j－１
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（２≤ｊ≤ｎ，１≤ｉ≤ｎ）
当求最小得分总和时
f〔i，j〕＝min｛f〔i，k〕＋f〔x，j－k〕＋t｝
１≤k≤j－１
c〔i，j〕＝k│ f〔i，j〕＝f〔i，k〕＋f〔x，j-k〕＋t
（２≤ｊ≤ｎ，１≤ｉ≤ｎ）
其中x＝（i＋k－１）modn＋１，即第i堆数起，顺时针数k＋１堆的堆序号。
对每一堆石子来说，它的
f〔i，１〕＝０
c〔i，１〕＝０ （１≤i≤N）
对于子序列〔i，j〕来说，若求最小得分总和，f〔i，j〕的初始值为∞； 若求最大得分总和，f〔i，j〕的初始值为０。（１≤i≤N，２≤j≤N）。
例如对例子中的６(３ ４ ６ ５ ４ ２ )堆石子，按动态规划方程顺推最小得分和。 依次得出含二堆石子的６个子序列的合并方案
f〔１，２〕＝７ f〔２，２〕＝１０ f〔３ ，２〕＝１１
c〔１，２〕＝１ c〔２，２〕＝１ c〔３，２〕＝１
f〔４，２〕＝９ f〔５，２〕＝６ f〔６，２〕＝５
c〔４，２〕＝１ c〔５， ２〕＝１ c〔６，２〕＝１
含三堆石子的６(３ ４ ６ ５ ４
２ )个子序列的合并方案
f〔１，３〕＝２０ f〔２，３〕＝２５ f〔３，３〕＝２４
c〔１，３〕＝２ c〔２，３〕＝２ c〔３，３〕＝１
f〔４，３〕＝１７ f〔５，３〕＝１４ f〔６，３〕＝１４
c〔４，３〕＝１ c〔５，３〕＝１ c〔６，３〕＝２
含四堆石子的６(３ ４ ６ ５ ４
２ )个子序列的合并方案
f〔１，４〕＝３６ f〔２，４〕＝３８ f〔３，４〕＝３４
c〔１，４〕＝２ c〔２，４〕＝２ c〔３，４〕＝１
f〔４，４〕＝２８ f〔５，４〕＝２６ f〔６，４〕＝２９
c〔４，４〕＝１ c〔５，４〕＝２ c〔６，４〕＝３
含五堆石子的６(３ ４ ６ ５ ４
２ )个子序列的合并方案
f〔１，５〕＝５１ f〔２，５〕＝４８ f〔３，５〕＝４５
c〔１，５〕＝３ c〔２，５〕＝２ c〔３，５〕＝２
f〔４，５〕＝４１ f〔５，５〕＝４３ f〔６，５〕＝４５
c〔４，５〕＝２ c〔５，５〕＝３ c〔６，５〕＝３
含六堆石子的６(３ ４ ６ ５ ４
２ )个子序列的合并方案
f〔１，６〕＝６１ f〔２，６〕＝６２ f〔３，６〕＝６１
c〔１，６〕＝３ c〔２，６〕＝２ c〔３，６〕＝２
f〔４，６〕＝６１ f〔５，６〕＝６１ f〔６，６〕＝６２
c〔４，６〕＝３ c〔５，６〕＝４ c〔６，６〕＝３
f〔１，６〕是f〔１，６〕，ｆ〔２，６〕，……f〔６，６〕中的最小值，表明最小得分和是由序列〔１，６〕经５次合并得出的。我们从这个序列出发，
按下述方法倒推合并过程：
由c〔１，６〕＝３可知，第５次合并的两堆石子分别由子序列〔１，３〕和子序列〔４，3〕经４次合并后得出。其中c〔１，３〕＝２可知由子序列〔１，３〕合并成的一堆石子是由子序列〔１，２〕和第三堆合并而来的。而c〔１，２〕＝１，以表明了子序列〔１，２〕的合并方案是第１堆合并第２堆。
由此倒推回去，得出第１，第２次合并的方案，每次合并得分
第一次合并 ３ ４ ６…… ->７
第二次合并 ７ ６……
->１３
１３……
子序列〔１，３〕经２次合并后合并成１堆， ２次合并的得分和＝７＋１３＝２０。
ｃ〔４，３〕＝１，可知由子序列〔４，３〕合并成的一堆石子是由第４堆和子序列〔５，
２〕合并而来的。而c〔５，２〕＝１，又表明了子序列〔５，２〕的合并方案是第５堆合并第６堆。由此倒推回去，得出第３、第４次合并的方案
每次合并得分：
第三次合并 ……５４ ２ ->６
第四次合并 ……５ ６ ->１１
……１１
子序列〔４，３〕经２次合并后合并成１堆，２次合并的得分和＝６＋１１＝１７。
第五次合并是将最后两堆合并成１堆，该次合并的得分为２４。
显然，上述５次合并的得分总和为最小
２０＋１７＋２４＝６１
下面分析下代码的实现过程
1.初始化grades和ks的值
/*
初始化Grades和ks的值
choice为1表示求最多得分，为0为求最少得分
n表示有n堆石子
*/
void init(int **grades,int **ks,int choice,int n){
//给计算得分的数组赋初值
if(choice==1){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
grades[i][j]=0;
ks[i][j]=0;
}
}
}else{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j==1){
grades[i][j]=0;
}else{
grades[i][j]=999999;
}
ks[i][j]=0;
}
}
}
}
2.计算子问题的最少得分
/*
计算从start堆开始，计算count堆石子的最少得分
stoneCounts储存所有堆的石子数
leastGrades[start,count]对应的最少得分
ks[start,count]记录第start到第start+count间的k值，1=<k<=(count-1)
*/
void getMiniGrade(int *stoneCounts,int **leastGrades,int **ks,int start,int count,int n){
if(count>1){
int countStones=0;
//计算石子数
for(int j=0;j<count;j++){
countStones=countStones+stoneCounts[start+j];
}
int grade=999999;
for(int i=1;i<count;i++){
int k=(start+i-1)%n+1;
// cout<<" 中间值："<<i<<">>>>"<<leastGrades[start][i]<<" k:"<<k<<" "<<leastGrades[k][count-i]<<endl;
int newgrade=leastGrades[start][i]+leastGrades[k][count-i]+countStones;
//cout<<"最小成绩："<<newgrade<<endl;
if(newgrade<grade){
grade=newgrade;
ks[start][count]=i;
}
}
leastGrades[start][count]=grade;
//cout<<"start::"<<start<<"最小值："<<leastGrades[start][count]<<" c的值："<<ks[start][count]<<endl;
}
}
3.计算所有子问题的最少得分
/*
计算所有子问题的最少得分
*/
void getEachMiniGrades(int *stoneCounts,int **leastGrades,int **ks,int n){
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++){
getMiniGrade(stoneCounts,leastGrades,ks,i,j,n);
}
}
}
4.获得最少得分
/*
获得最少得分
*/
int miniGrade(int *stoneCounts,int **leastGrades,int **ks,int n){
getEachMiniGrades(stoneCounts,leastGrades,ks,n);
int mini=999999;
for(int i=1;i<=n;i++){
int newMini=leastGrades[i][n];
if(newMini<mini){mini=newMini;}
}
return mini;
}
5.计算子问题的最多得分
/*
计算从start堆开始，计算count堆石子的最多得分
*/
void getMaxGrades(int *stoneCounts,int **maxGrades,int **ks,int start,int count,int n){
if(count>1){
int countStones=0;
//计算石子数
for(int j=0;j<count;j++){
countStones=countStones+stoneCounts[start+j];
}
int grade=0;
for(int i=1;i<count;i++){
int k=(start+i-1)%n+1;
int newgrade=maxGrades[start][i]+maxGrades[k][count-i]+countStones;
if(newgrade>grade){
grade=newgrade;
ks[start][count]=i;
}
}
maxGrades[start][count]=grade;
}
}
6.计算每个子问题的最多得分
/*
计算所有子问题的最多得分
*/
void getEachMaxiGrades(int *stoneCounts,int **maxGrades,int **ks,int n){
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++){
getMaxGrades(stoneCounts,maxGrades,ks,i,j,n);
}
}
}
7.获得最多得分
/*
获得最多得分
*/
int maxGrade(int *stoneCounts,int **maxGrades,int **ks,int n){
getEachMaxiGrades(stoneCounts,maxGrades,ks,n);
int max=0;
for(int i=1;i<=n;i++){
int newMax=maxGrades[i][n];
if(newMax>max){max=newMax;}
}
return max;
}
8.显示每堆石子的数量
/*
显示各堆石子的数量
*/
void showStones(int *stoneCounts,int n){
cout<<"各堆石子数："<<n<<endl;
int count=0;
for(int i=1;i<=(n-1);i++){
count++;
cout<<stoneCounts[i]<<"\t";
if(count==6){count=0;cout<<endl;}
}
cout<<endl;
}
9.显示所有子问题的得分情况
/*
显示各子问题所得分数
*/
void showGrades(int **grades,int n){
cout<<"所得分数："<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<grades[i][j]<<"\t";
}
cout<<endl;
}
cout<<endl;
}
10.main函数的内容
void main(){
FILE *fin,*fout;
int n,*stoneCounts,**leastGrades,**maxGrades,**ksMini,**ksMax;
if((fin=fopen("input2.txt","r"))==NULL)
printf("Read error!!");
fscanf(fin,"%d",&n);
fclose(fin);
stoneCounts =new int [2*n];
leastGrades = (int **)malloc((n + 1) * sizeof(int *));
maxGrades =(int **)malloc((n + 1) * sizeof(int *));
ksMini =(int **)malloc((n + 1) * sizeof(int *));
ksMax=(int **)malloc((n + 1) * sizeof(int *));
for(int i = 0; i<= n; i++){
leastGrades[i] = (int *)malloc((n + 1) * sizeof(int));
maxGrades[i] = (int *)malloc((n + 1) * sizeof(int));
ksMini[i] = (int *)malloc((n + 1) * sizeof(int));
ksMax[i] = (int *)malloc((n + 1) * sizeof(int));
}
init(leastGrades,ksMini,0,n);
init(maxGrades,ksMax,1,n);
if((fin=fopen("input2.txt","r"))==NULL)
printf("Read error!!\n");
fscanf(fin,"%d",&n);
for(int j=1;j<=n;j++){
fscanf(fin,"%d",&stoneCounts[j]);
}
fclose(fin);
for(int k=n+1;k<=(2*n-1);k++){
stoneCounts[k]=stoneCounts[k-n];
}
showStones(stoneCounts,2*n);
int mini=miniGrade(stoneCounts,leastGrades,ksMini,n);
cout<<"最少得分的子问题："<<endl;
showGrades(leastGrades,n);
int max=maxGrade(stoneCounts,maxGrades,ksMax,n);
cout<<"最多得分的子问题："<<endl;
showGrades(maxGrades,n);
cout<<"最小值："<<mini<<"最大值："<<max<<endl;
fout=fopen("output2.txt","w");
fprintf(fout,"%d\n",mini);
fprintf(fout,"%d\n",max);
fclose(fout);
}
源代码和对石子合并问题的详细解说文档在上上传文件里
分享到：
相关推荐
//--石子合并问题 /*问题描述：在一个圆形操场的四周摆放着n堆石子，先要将石子有序的合并为一堆。规定每次只能选相邻的石子合并成一堆，并将新一堆的石子数 记录为该次合并的得分。试设计一个算法，记录n堆石子...
针对石子合并问题，本文利用动态规划算法寻求石子合并时的最大,最小得分，选择相邻的两堆石子堆进行合并，其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程，利用程序进行求解。算例结果...
动态规划 解决石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只 能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出...
用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题
算法分析课程作业，C语言编写，可能需要用input.txt输入，石子合并问题代码
动态规划解石子合并问题，其中石子呈环形排列。源程序为c++代码。
需要交作业的，可以考虑下载哦。是关于石子合并问题
石子合并问题可运行Java源码，下载到Eclipse就可以运行了。 要求在工程根目录下有input.txt文件，结果output.txt会生成在相同目录下
实现3-3石子合并问题.cpp
C语言实现的石子合并问题，自己可以改成其他的语言，这是核心语句
规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务： 对于给定n堆石子,编程计算合并成一堆的最小...
问题描述：在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选择相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
用动态规划方法解决石子合并问题，很不错的一个算法！嘿嘿......
自己实现的 。实现的一个算法。容易懂的 自己实现的 。实现的一个算法。容易懂的
石子归并问题：在一个圆形操场的四周摆放着N堆石子(N<= 100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每...
Problem D:石子合并（包含源程序c++） Time Limit:1000MS Memory Limit:65536K Description 在一个圆形操场的四周摆放着 n 堆石子. 现要将石子有次序地合并成一堆, 规定每次只能选相邻的 2 堆石子合并成新的一堆, ...
第一个石子合并模型,和书上3.1节的矩阵连乘问题类似. 假设m[i,j]为合并石子ai…aj, 1≤i≤j≤n，所得到的最小得分，若没有“合并”这个动作，则为0。原问题所求的合并最小值即为m[1,n]。 递推公式如下,其中min表示...