问题描述:
在一个园形操场的四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆。规定
每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
编一程序,由文件读入堆数N及每堆的石子数(≤20),
①选择一种合并石子的方案,使得做N-1次合并,得分的总和最小;
②选择一种合并石子的方案,使得做N-1次合并,得分的总和最大。
例如,所示的4堆石子,每堆石子数(从最上面的一堆数起,顺时针数)依
次为4594。则3次合并得分总和最小的方案:8+13+22=43
得分最大的方案为:14+18+22=54
该问题应该用动态规划算法才能得到最优解,而贪心算法得不到最优解。
而动态规划算法的基本要素是:最优子结构和重叠子问题
针对该问题,我们用f(i,j)表示从第i堆石子数起,顺时针数j堆石子的得分,则它的动态规划方程为
当求最大得分总和时
f〔i,j〕=max{f〔i,k〕+f〔x,j-k〕+t}
1≤k≤j-1
c〔i,j〕=k│ f〔i,j〕=f〔i,k〕+f〔x,j-k〕+t
(2≤j≤n,1≤i≤n)
当求最小得分总和时
f〔i,j〕=min{f〔i,k〕+f〔x,j-k〕+t}
1≤k≤j-1
c〔i,j〕=k│ f〔i,j〕=f〔i,k〕+f〔x,j-k〕+t
(2≤j≤n,1≤i≤n)
其中x=(i+k-1)modn+1,即第i堆数起,顺时针数k+1堆的堆序号。
对每一堆石子来说,它的
f〔i,1〕=0
c〔i,1〕=0 (1≤i≤N)
对于子序列〔i,j〕来说,若求最小得分总和,f〔i,j〕的初始值为∞; 若求最大得分总和,f〔i,j〕的初始值为0。(1≤i≤N,2≤j≤N)。
例如对例子中的6(3 4 6 5 4 2 )堆石子,按动态规划方程顺推最小得分和。 依次得出含二堆石子的6个子序列的合并方案
f〔1,2〕=7 f〔2,2〕=10 f〔3 ,2〕=11
c〔1,2〕=1 c〔2,2〕=1 c〔3,2〕=1
f〔4,2〕=9 f〔5,2〕=6 f〔6,2〕=5
c〔4,2〕=1 c〔5, 2〕=1 c〔6,2〕=1
含三堆石子的6(3 4 6 5 4
2 )个子序列的合并方案
f〔1,3〕=20 f〔2,3〕=25 f〔3,3〕=24
c〔1,3〕=2 c〔2,3〕=2 c〔3,3〕=1
f〔4,3〕=17 f〔5,3〕=14 f〔6,3〕=14
c〔4,3〕=1 c〔5,3〕=1 c〔6,3〕=2
含四堆石子的6(3 4 6 5 4
2 )个子序列的合并方案
f〔1,4〕=36 f〔2,4〕=38 f〔3,4〕=34
c〔1,4〕=2 c〔2,4〕=2 c〔3,4〕=1
f〔4,4〕=28 f〔5,4〕=26 f〔6,4〕=29
c〔4,4〕=1 c〔5,4〕=2 c〔6,4〕=3
含五堆石子的6(3 4 6 5 4
2 )个子序列的合并方案
f〔1,5〕=51 f〔2,5〕=48 f〔3,5〕=45
c〔1,5〕=3 c〔2,5〕=2 c〔3,5〕=2
f〔4,5〕=41 f〔5,5〕=43 f〔6,5〕=45
c〔4,5〕=2 c〔5,5〕=3 c〔6,5〕=3
含六堆石子的6(3 4 6 5 4
2 )个子序列的合并方案
f〔1,6〕=61 f〔2,6〕=62 f〔3,6〕=61
c〔1,6〕=3 c〔2,6〕=2 c〔3,6〕=2
f〔4,6〕=61 f〔5,6〕=61 f〔6,6〕=62
c〔4,6〕=3 c〔5,6〕=4 c〔6,6〕=3
f〔1,6〕是f〔1,6〕,f〔2,6〕,……f〔6,6〕中的最小值,表明最小得分和是由序列〔1,6〕经5次合并得出的。我们从这个序列出发,
按下述方法倒推合并过程:
由c〔1,6〕=3可知,第5次合并的两堆石子分别由子序列〔1,3〕和子序列〔4,3〕经4次合并后得出。其中c〔1,3〕=2可知由子序列〔1,3〕合并成的一堆石子是由子序列〔1,2〕和第三堆合并而来的。而c〔1,2〕=1,以表明了子序列〔1,2〕的合并方案是第1堆合并第2堆。
由此倒推回去,得出第1,第2次合并的方案,每次合并得分
第一次合并 3 4 6…… ->7
第二次合并 7 6……
->13
13……
子序列〔1,3〕经2次合并后合并成1堆, 2次合并的得分和=7+13=20。
c〔4,3〕=1,可知由子序列〔4,3〕合并成的一堆石子是由第4堆和子序列〔5,
2〕合并而来的。而c〔5,2〕=1,又表明了子序列〔5,2〕的合并方案是第5堆合并第6堆。由此倒推回去,得出第3、第4次合并的方案
每次合并得分:
第三次合并 ……54 2 ->6
第四次合并 ……5 6 ->11
……11
子序列〔4,3〕经2次合并后合并成1堆,2次合并的得分和=6+11=17。
第五次合并是将最后两堆合并成1堆,该次合并的得分为24。
显然,上述5次合并的得分总和为最小
20+17+24=61
下面分析下代码的实现过程
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堆石子,目标是通过相邻两堆石子的合并,...
针对石子合并问题,本文利用动态规划算法寻求石子合并时的最大,最小得分,选择相邻的两堆石子堆进行合并,其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程,利用程序进行求解。算例结果...
动态规划 解决石子合并问题 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只 能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出...
在这个“石子合并问题”中,我们面临的就是这样一个挑战。问题描述可能涉及在环形排列的石子上进行一系列合并操作,每次操作可以将相邻的两堆石子合并成一堆,消耗一定的能量。目标可能是最小化完成所有合并操作所需...
用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题 用 动态规划 解决 石子合并 问题
算法分析课程作业,C语言编写,可能需要用input.txt输入,石子合并问题代码
石子合并问题可运行Java源码,下载到Eclipse就可以运行了。 要求在工程根目录下有input.txt文件,结果output.txt会生成在相同目录下
实现3-3石子合并问题.cpp
### 石子合并问题与动态规划 #### 一、问题背景及定义 在计算机科学领域,特别是算法设计中,石子合并问题是常见的一个问题。该问题通常可以这样描述:假设有一行排布的N个石子,每个石子有一个特定的分数。玩家的...
### 石子合并问题解析与算法实现 #### 知识点概述 石子合并问题是在计算机科学领域中一种经典的动态规划问题,它涉及到数组、循环、动态规划算法以及位运算等核心概念。在这个问题中,我们需要在一个圆形操场的...
C语言实现的石子合并问题,自己可以改成其他的语言,这是核心语句
### 石子合并问题分析与Java实现 #### 一、问题背景及定义 在一个圆形操场的四周摆放着\( n \)堆石子。任务是将这些石子有序地合并成一堆。每次只能选择两堆相邻的石子进行合并,新合并的一堆石子数为这两堆石子数...
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 编程任务: 对于给定n堆石子,编程计算合并成一堆的最小...
标题中的“石子合并问题”通常是指一个计算机科学或算法设计中的经典问题,它与数据结构和动态规划等基础知识紧密相关。在这个问题中,我们通常想象有若干堆石子,每堆有不同的数量,两个玩家轮流从任一堆中取走一定...
### 算法设计——石子合并问题 #### 背景介绍 在算法设计领域,特别是针对优化问题的研究中,“石子合并问题”是一种典型的动态规划应用案例。该问题通常表述为:在一个直线上放置若干堆石子,每堆石子的数量已知。...