石子合并问题_C/C++_编程开发_程序员俱乐部

问题描述：

??在一个园形操场的四周摆放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);
}

??源代码和对石子合并问题的详细解说文档在上上传文件里