石子合并问题 三种类型

《石子合并问题 三种类型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一：任意版有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。此类问题比较简单，就是哈夫曼编码的变形，用贪心算法即可求得最优解。即每次选两堆最少的，合并成新的一堆，直到只剩一堆为止。证明过程可以参考哈夫曼的证明过程。二：直线版在一条直线上摆着N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。如果熟悉矩阵连乘对这类问题肯定非常了解。矩阵

2、连乘每次也是合并相邻两个矩阵（只是计算方式不同）。那么石子合并问题可用矩阵连乘的方法来解决。那么最优子结构是什么呢？如果有N堆，第一次操作肯定是从n-1个对中选取一对进行合并，第二次从n-2对中选取一对进行合并，以此类推……设best[i][j]表示i-j合并的最优值,sum[i][j]表示第i堆石子到第j堆石子的总数量，递推公式如下：#include#include#include#includeusingnamespacestd;#defineMAXN100intsum[MAXN];intbest

3、[MAXN][MAXN];intn,stone[MAXN];intgetBest(){//初始化，没有合并，花费为0for(inti=0;i0?sum[i-1]:0);//中间断开位置，取最优值for(intk=i;k

4、=min(best[i][j],best[i][k]+best[k+1][j]+add);}}}returnbest[0][n-1];}intmain(){scanf("%d",&n);for(inti=0;i

5、一想，似乎与直线排列完全成了两个不同的问题。因为每次合并后我们都要考虑最后一个与第一个的合并关系。直线版的矩阵连乘对角线式的最优子结构不见了。f(i,j)表示i-j合并的最优值似乎并不可行，因为我们可以得到的最优值第一步就是第一个与最后一个合并，那么f(i,j)并不能表示这种关系。修改一下，f(i,j)表示从第i个开始，合并后面j个得到的最优值。sum(i,j)表示从第i个开始直到i+j个的数量和。那么这个问题就得到解决了。注意要把其看成环形，即在有限域内的合并。递推公式如下： #include   #include   #includ

6、e   #include   using namespace std;    #define  MAXN 100  int sum[MAXN];  int mins[MAXN][MAXN], maxs[MAXN][MAXN];    int n, stone[MAXN];  int sums(int i, int j) {  if(i + j >= n) {          return sums(i, n - i - 1) + sums(0, (i + j) % n);  } else{       return sum[i + 

7、j] - (i > 0 ? sum[i - 1] : 0);    }  }    void getBest(int& minnum, int& maxnum) {   //初始化，没有合并，花费为0   for(int i = 0; i < n; ++i) {   mins[i][0] = maxs[i][0] = 0;  }  //还需进行合并次数    for(int j = 1; j < n; ++j) {  for(int i = 0; i < n; ++i) {  mins[i][j] = INT_MAX;    maxs[i