欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划思想:石子合并问题

程序员文章站 2022-07-03 08:50:00
...
描述:
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。
试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。


动态规划思想:石子合并问题


开始以为通过贪心算法可能很快解决问题,可是是行不通的。

      首先我们可以把这么堆石子看成一列

      我们假如5堆的石子,其中石子数分别为7,6,5,7,100

      •按照贪心法,合并的过程如下:
        每次合并得分
        第一次合并  7  6   5   7    100   =11
      第二次合并  7   11     7   100=18
      第三次合并  18    7    100 =25
        第四次合并   25   100 =125

        总得分=11+18+25+125=179

       •另一种合并方案

        每次合并得分
     第一次合并  7  6   5   7    100   ->13
         第二次合并  13   5     7   100->12
         第三次合并  13    12    100 ->25
         第四次合并   25   100 ->125

         总得分=13+12+25+125=175

         显然利用贪心来做是错误的,贪心算法在子过程中得出的解只是局部最优,而不能保证使得全局的值最优。

    

         如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。

     因此我们需要通过动态规划算法来求出最优解。

 

         在此我们假设有n堆石子,一字排开,合并相邻两堆的石子,每合并两堆石子得到一个分数,最终合并后总分数最少的。

   我们设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堆时......

 

        代码实现如下:



开始以为通过贪心算法可能很快解决问题,可是是行不通的。

      首先我们可以把这么堆石子看成一列

      我们假如5堆的石子,其中石子数分别为7,6,5,7,100

      •按照贪心法,合并的过程如下:
        每次合并得分
        第一次合并  7  6   5   7    100   =11
      第二次合并  7   11     7   100=18
      第三次合并  18    7    100 =25
        第四次合并   25   100 =125

        总得分=11+18+25+125=179

       •另一种合并方案

        每次合并得分
     第一次合并  7  6   5   7    100   ->13
         第二次合并  13   5     7   100->12
         第三次合并  13    12    100 ->25
         第四次合并   25   100 ->125

         总得分=13+12+25+125=175

         显然利用贪心来做是错误的,贪心算法在子过程中得出的解只是局部最优,而不能保证使得全局的值最优。

    

         如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。

     因此我们需要通过动态规划算法来求出最优解。

 

         在此我们假设有n堆石子,一字排开,合并相邻两堆的石子,每合并两堆石子得到一个分数,最终合并后总分数最少的。

   我们设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堆时......

 

        代码实现如下:

开始以为通过贪心算法可能很快解决问题,可是是行不通的。

      首先我们可以把这么堆石子看成一列

      我们假如5堆的石子,其中石子数分别为7,6,5,7,100

      •按照贪心法,合并的过程如下:
        每次合并得分
        第一次合并  7  6   5   7    100   =11
      第二次合并  7   11     7   100=18
      第三次合并  18    7    100 =25
        第四次合并   25   100 =125

        总得分=11+18+25+125=179

       •另一种合并方案

        每次合并得分
     第一次合并  7  6   5   7    100   ->13
         第二次合并  13   5     7   100->12
         第三次合并  13    12    100 ->25
         第四次合并   25   100 ->125

         总得分=13+12+25+125=175

         显然利用贪心来做是错误的,贪心算法在子过程中得出的解只是局部最优,而不能保证使得全局的值最优。

    

         如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。

     因此我们需要通过动态规划算法来求出最优解。

 

         在此我们假设有n堆石子,一字排开,合并相邻两堆的石子,每合并两堆石子得到一个分数,最终合并后总分数最少的。

   我们设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堆时......

 

        代码实现如下:

#include<stdio.h>
 #define N 100
 /*
 *求合并过程中
 *最少合并堆数目
 **/
 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;

                                                          //当一个单独合并时,m[i][i]设为0,表示没有石子
     for(int g = 1;g<=n;g++) m[g][g]=0;

                                                          //当相邻的两堆石子合并时,此时的m很容易可以看出是两者之和
     for(int i=1;i<=n-1;i++)
    {
        int j=i+1;
        m[i][j]=p[i]+p[j];
    }

                                                          //当相邻的3堆以及到最后的n堆时,执行以下循环
    for(int r=3; r<=n;r++)
         for(int i=1;i<=n-r+1;i++)
         {
             int j = i+r-1;                               //j总是距离i   r-1的距离
             int sum=0;
                                                          //当i到j堆石子合并时最后里面的石子数求和得sum
             for(int b=i;b<=j;b++)
                 sum+=p[b];

             // 此时m[i][j]为i~j堆石子间以m[i][i]+m[i+1][j]+sum结果,这是其中一种可能,不一定是最优
             //要与下面的情况相比较,唉,太详细了

             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;

             }
         }
          //最终得到最优解
         min=m[1][n];
         return min;

        
}

/*
 *求合并过程中
 *最多合并堆数目
 **/

  int  MatrixChain_max(int p[N],int n)
{
       int m[N][N];
         for(int x=1;x<=n;x++)
        for(int z=1;z<=n;z++)
        {
            m[x][z]=-1;           
        }


     int max=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];
    }

    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;

             }
         }

         max=m[1][n];
         return max;

        
}
int main()
{
      int stone[N];
      int min=0;
      int max=0;
      int n;
      scanf("%d",&n);
      for(int i=1;i<=n;i++)
          scanf("%d",&stone[i]);

      min= MatrixChain_min(stone,n);
      max= MatrixChain_max(stone,n);

      //因为题目要求圆的原因,要把所有情况都要考虑到,总共有n种情况。
      for(int j=1;j<=n-1;j++)
      {
           int min_cache=0;
           int max_cache=0;
           int cache= stone[1];
           for(int k=2;k<=n;k++)
           {
               stone[k-1]=stone[k];
           }
           stone[n]=cache;
           min_cache= MatrixChain_min(stone,n);
           max_cache= MatrixChain_max(stone,n);
           if(min_cache<min)
               min=min_cache;
           if(max_cache>max)
               max=max_cache;
      }
   
    printf("%d\n",min);
    printf("%d\n",max);

    return 1;

}