精华内容
下载资源
问答
  • 石子合并问题
    2021-04-06 16:03:39

    石子合并问题

    一、问题描述

    【问题简述】
    在一个园形操场的四周摆放n堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。试设计一个算法,计算出将n堆石子合成一堆的最小得分和最大得分。
    【输入形式】
    输入数据由文件名为input.txt的文本文件提供。文件的第1行为正整数n(1≤n≤100),表示有n堆石子;第二行有n个数,分别表示每堆石子的个数。
    【输出形式】
    将计算结果输出到文件output.txt。输出文件有两行,分别为得分最小的合并方案数值和得分最大合并方案数值。

    二、问题分析

    ​ 为了尽可能逼近目标的贪心法来逐次合并:从最上面的一堆开始,沿顺时针方向排成一个序列。 第一次选得分最小(最大)的相邻两堆合并,形成新的一堆;接下来,在 n-1 堆中选得分最小(最大)的相邻两堆合并……,依次类推, 直至所有石子经 n-1 次合并后形成一堆。
    ​ 例如有6堆石子,每堆石子数(从最上面一堆数起,顺时针数)依次为
    3 46 5 4 2 若要使得得分的总和最小。
    按照贪心法,合并的过程如下:
    ​ 第一次 3 4 6 5 4 2 -> 5
    ​ 第二次 5 4 6 5 4 -> 9
    ​ 第三次 9 6 5 4 -> 9
    ​ 第四次9 6 9 -> 15
    ​ 第五次 15 9 -> 24
    ​ 总得分=5+9+9+15+24=62
    但可得出另一个合并石子的方案:
    ​ 第一次3 4 6 5 4 2 -> 7
    ​ 第二次 7 6 5 4 2 -> 13
    ​ 第三次 13 5 4 2 -> 6
    ​ 第四次 13 5 6 -> 11
    ​ 第五次 13 11 -> 24
    ​ 总得分=7+13+6+11+24=61
    显然,后者比贪心法得出的合并方案更优。
    ​ 使用贪心法可能出错,是因为每一次选择得分最小(最大)的相邻两堆合并,不一定保证余下的合并过程能导致最优解。
    ​ 故采用动态规划求解:如果N-1的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的。

    三、算法设计

    采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。
    这些石子堆子序列包括:
    {第1堆、第2堆}{第2堆、第3堆}…{第N堆、第1堆};
    {第1堆、第2堆、第3堆}{第2堆、第3堆、第4堆}…{第N堆、第1堆、第2堆};…
    {第1堆、…、第N堆}{第2堆、…、第N堆、第1堆}…{第N堆、第1堆、…、第N-1堆}
    为了便于运算,我们用〔i,j〕表示一个从第i堆数起,顺时针数j堆时的子序列{第i堆、第i+1堆、……、第(i+j-1)mod n堆}它的最佳合并方案包括两个信息:
    ①在该子序列的各堆石子合并成一堆的过程中,各次合并得分的总和;
    ②形成最佳得分和的子序列1和子序列2。由于两个子序列是相邻的,因此只需记住子序列1的堆数;
    f〔i,j〕──将子序列〔i,j〕中的j堆石子合并成一堆的最佳得分和;
    c〔i,j〕──将〔i,j〕一分为二,其中子序列1的堆数;(1≤i≤N,1≤j≤N)
    显然,对每一堆石子来说,它的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)
    动态规划的方向是顺推(即从上而下):
    先考虑含二堆石子的N个子序列(各子序列分别从第1堆、第2堆、……、第N堆数起,顺时针数2堆)的合:
    f〔1,2〕,f〔2,2〕,……,f〔N,2〕
    c〔1,2〕,c〔2,2〕,……,c〔N,2〕
    然后考虑含三堆石子的N个子序列(各子序列分别从第1堆、第2堆、……、第N堆数起,顺时针数3堆)的合并方案:
    f〔1,3〕,f〔2,3〕,……,f〔N,3〕
    c〔1,3〕,c〔2,3〕,……,c〔N,3〕
    依次类推,直至考虑了含N堆石子的N个子序列(各子序列分别从第1堆、第2堆、……、第N堆数起,顺时针数N堆)的合并方案:
    f〔1,N〕,f〔2,N〕,……,f〔N,N〕
    c〔1,N〕,c〔2,N〕,……,c〔N,N〕
    最后,在子序列〔1,N〕,〔2,N〕,……,〔N,N〕中,选择得分总和最小或最大。

    四、关键代码

    【初始化数组】

    file.open("input.txt",ios::in);		//打开输入文件
    file>>n;
    int A[2*n+1],B[2*n+1];
    B[0]=0;
    // 初始化数组
    for (int i=1;i<=n;i++) {
        file>>a;
        A[i]=a;
        A[i+n]=A[i];
    }
    // 计算最大和
    for (int i=1;i<=2*n;i++) {
        B[i]=B[i-1]+A[i];
    }
    file.close();	//关闭输入文件 
    

    【递归方程】

     // 开始递归循环
        for(int i=2*n-1;i>0;i--) 
    	{
            for(int j=i+1;j<i+n;j++)
    		{
    			Min[i][j] = INF; //#define INF 0x3f3f3f3f
                for(int k=i;k<j;k++) 
    			{
    				//这里相当于在第i堆与第j堆中间选择了第k堆作为中间值,在之前我们已经算好了最大和数组B[]
    				//Min[i][k]相当于在i,k中间取石子的最小值+M[k+1][j]表示在k+1,j之间取石子的最小值
                    //B[j]-B[i-1]就表示i-j石子加的和
                    Min[i][j]=min(Min[i][j],Min[i][k]+Min[k+1][j]+B[j]-B[i-1]);
                    Max[i][j]=max(Max[i][j],Max[i][k]+Max[k+1][j]+B[j]-B[i-1]);
                }
            }
        }
    

    【遍历找到最大与最小值】

    int MaxNum=Max[1][n],MinNum=Min[1][n];
    for (int i = 1; i <= n; i++) {
        MaxNum=max(MaxNum,Max[i][i+n-1]);//得分最大
        MinNum=min(MinNum,Min[i][i+n-1]);//得分最小
    }
    

    五、实验心得

    【贪心法和动态规划法的比较】
    动态规划法:
    [基本思想与策略]
    动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。
    [适用情况]
      (1)最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
      (2)无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
      (3)有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
     贪心算法:
    [基本思想与策略]
    贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题,要确定它是否具有贪心选择的性质,我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解,是从贪心选择开始的,而且作了贪心选择后,原问题简化为一个规模更小的类似子问题。然后,用数学归纳法证明,通过每一步贪心选择,最终可得到问题的一个整体最优解。
    [适用情况]
      随着算法的进行,将积累起其它两个集合:一个包含已经被考虑过并被选出的候选对象,另一个包含已经被考虑过但被丢弃的候选对象。
      有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
      还有一个函数检查是否一个候选对象的集合是可行的,也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样,此时不考虑解决方法的最优性。
      选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。
      最后,目标函数给出解的值。
    【实验心得】
    石子合并问题很容易把贪心法和动态规划法弄混,区分二者很简单,就是看题目是否包含二者的问题性质,贪心法需要具有最优子结构,且具有局部最优代替整体最优的性质,而动态规划算法一定要具最优子结构性质。
    其次这个问题和我们之前遇到的凸多边形最优三角剖分和矩阵连乘非常类似。因为它们都是在找子问题、子结构。在不同的位置就问题分开成多个不同的子问题,对这些子问题求最优,然后从将子问题合并得到原问题,就达到了最优子结构的性质。

    六、实验源码

    #include<iostream>
    #include<fstream>
    #define INF 0x3f3f3f3f
    using namespace std;
    int Max[201][201],Min[201][201];
    int main()
    {
    	fstream file;
    	int n,a;
    	file.open("input.txt",ios::in);		//打开输入文件
    	file>>n;
    	int A[2*n+2],B[2*n+2];
    	B[0]=0;
    	// 初始化数组
    	for (int i=1;i<=n;i++) 
    	{
            file>>a;
            A[i]=a;
            A[i+n]=A[i];
    	}
    	file.close();	//关闭输入文件 
    	// 计算最大和
        for (int i=1;i<=2*n;i++) 
    	{
             B[i]=B[i-1]+A[i];
        }
        // 开始递归循环
        for(int i=2*n-1;i>0;i--) 
    	{
            for(int j=i+1;j<i+n;j++)
    		{
    			Min[i][j] = INF;
                for(int k=i;k<j;k++) 
    			{
    				//这里相当于在第i堆与第j堆中间选择了第k堆作为中间值,在之前我们已经算好了最大和数组B[]
    				//Min[i][k]相当于在i,k中间取石子的最小值+M[k+1][j]表示在k+1,j之间取石子的最小值
                    //B[j]-B[i-1]就表示i-j石子加的和
                    Min[i][j]=min(Min[i][j],Min[i][k]+Min[k+1][j]+B[j]-B[i-1]);
                    Max[i][j]=max(Max[i][j],Max[i][k]+Max[k+1][j]+B[j]-B[i-1]);
                }
            }
        }
        // 遍历找到最大与最小值
        int MaxNum=Max[1][n],MinNum=Min[1][n];
        for (int i = 1; i <= n; i++) 
    	{
            MaxNum=max(MaxNum,Max[i][i+n-1]);
            MinNum=min(MinNum,Min[i][i+n-1]);
        }
    	file.open("output.txt",ios::out); 	//打开输出文件
        file<<MinNum<<endl<<MaxNum<<endl;		//将结果输出到输出文件 
        file.close();
        return 0;
    }
    
    更多相关内容
  • D - 石子合并问题 Description 在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将...

    D - 石子合并问题
    Description
    在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。
    对于给定n堆石子,计算合并成一堆的最小得分和最大得分。
    Input
    输入数据的第1行是正整数n,1≤n≤100,表示有n堆石子。第二行有n个数,分别表示每堆石子的个数。
    Output
    输出数据有两行,第1行中的数是最小得分,第2行中的数是最大得分。
    Sample
    Input
    4
    4 4 5 9
    Output
    43
    54

    #include<bits/stdc++.h>
    #define T 0x3f3f3f3f
    using namespace std;
    int main()
    {
        int n,i,j,k,s[205],a[205][205],b[205][205];
        cin>>n;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(i=1;i<=n;i++)
        {
            cin>>s[i];
            s[i+n]=s[i];
        }
        int sum[205];sum[0]=0;
        for(i=1;i<=2*n;i++)
        {
            sum[i]=sum[i-1]+s[i];
        }
        for(i=2*n-1;i>=1;i--)
        {
            for(j=i+1;j<i+n&&j<=2*n;j++)
            {
                b[i][j]=T;
                for(k=i;k<j;k++)
                {
                    a[i][j]=max(a[i][j],a[i][k]+a[k+1][j]+sum[j]-sum[i-1]);
                    b[i][j]=min(b[i][j],b[i][k]+b[k+1][j]+sum[j]-sum[i-1]);
                }
            }
        }
        int y=T,x=-1;
        for(i=1;i<=n;i++)//n个区间的值进行比较
        {
            y=min(y,b[i][i+n-1]);
            x=max(x,a[i][i+n-1]);
        }
        cout<<y<<endl;
        cout<<x<<endl;
        return 0;
    }
    
    
    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1005;
    int arr[maxn], sum[maxn];
    int Max[maxn][maxn], Min[maxn][maxn];
    int main()
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >> arr[i];
        }
        for(int i = n+1; i < 2*n; i++)
        {
            arr[i] = arr[i-n];
        }
        for(int i = 1; i < 2*n; i++)
            sum[i] = sum[i-1] + arr[i];
        for(int i = 2*n-1; i >= 1; i--)
        {
            for(int j = i+1; j < i+n; j++)
            {
                Min[i][j] = 0x3f3f3f3f;
                for(int k = i; k < j; k++)
                {
                    Max[i][j] = max(Max[i][j], Max[i][k] + Max[k+1][j] + sum[j] - sum[i-1]);
                    Min[i][j] = min(Min[i][j], Min[i][k] + Min[k+1][j] + sum[j] - sum[i-1]);
                }
            }
        }
        int Mx = 0, Mi = 0x3f3f3f3f;
        for(int i = 1; i <= n; i++)
        {
            Mx = max(Mx, Max[i][i+n-1]);
            Mi = min(Mi, Min[i][i+n-1]);
        }
        cout << Mi << endl << Mx << endl;
        return 0;
    }
    
    
    展开全文
  • C语言实现的石子合并问题,自己可以改成其他的语言,这是核心语句
  • 规定每次只能选择相邻的2堆石子合并成新的一堆,并将新的一堆石子数作为得分,尝设计一个算法,计算出n堆石子合并成一堆的最小分数和最大分数。 算法分析 dp[i][t]=min(dp[i][t],dp[i][k]+dp[(i+k-1)%n+1][t-k]+...

    问题

    在一个圆形的操场的四周摆上n堆石子,现在将石子有次序的合并成一堆。规定每次只能选择相邻的2堆石子合并成新的一堆,并将新的一堆石子数作为得分,尝设计一个算法,计算出n堆石子合并成一堆的最小分数和最大分数。

    算法分析

    • dp[i][t]=min(dp[i][t],dp[i][k]+dp[(i+k-1)%n+1][t-k]+sum(i,t))
    • dp[ i ][ t ]表示从 第i堆开始之后合并t堆石子(包括第i堆石子)合并花费。
    • k是i~t之间的一个数
    • 因为是环形,所以要将一维数组收尾相连,所以计算第i+k堆应该表示成: (i+k-1)%n+1,注意这里 不能想当然的以为-1%n可以和外面的1约掉就变成(k+1)%n, 这里是因为数组的下标是从1开始的, 前者可以保证不去到0.
    • sum表示最后两队合并时候的花费,一定等于所有石子的个数.
     

    dp算法的核心是将大问题装华为若干联席的子问题,先求解子问题,然后从这些子问题的解得到原问题的解;对于重复出现的子问题,只在第一次遇到的时候对它进行求解,并把答案保存起来,让以后再次遇到时直接引用答案,不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果,与贪婪算法不同的是,在贪婪算法中,每采用一次贪婪准则,便做出一个不可撤回的决策;而在动态规划算法中,还要考察每个最优决策序列中是否包含一个最优决策子序列,即问题是否具有最优子结构性质。在本题中可以把dp[ i ][ n ]看成一堆,这一堆的最优解是由 由这堆分割的两小堆合并的。 然后每两小堆又可以再分,知道分成两堆的石子合并,前面这部分是分治法的思想, 但是值得注意的是选择不同的堆作为第一堆,得到的结果不一样,这样如果每个每种情况都像这样分,就会有很多重复的,以致时间复杂度达到指数级, 所以我们要想办法吧子问题的结果保留下来, 然后再得到最优解.这就是动态规划的思想. 最普遍的做法是自底向上将子问题的保存在数组中.

     

    前三堆所构成的花费是由 三部分构成,1、第一二合并的花费;2、第一二合并的个数和;3:第三堆本身个数
    衍生一下,前四堆合并花费也一样由三部分,1、第一二三合并的花费,2、第一二三合并的个数和;3、第四堆本身个数
    这样就很明显了,把大问题分解成了小问题,而且大问题包含了小问题的解,大问题和小问题同质同解。完完全全满足dp的性质。
    比如以4堆作为例子当前是从1->2->3->4的顺序去合并的,还有(1->2)->(3->4)或者1->(2->3->4)的顺序,原理一样,这里面因为第二第三部分是固定的,所以只需要得到小问题的最优解,就可以求得大问题的最优解了。比如解决1->(2->3->4)中(2->3->4)的合并,到底是先2,3还是先3,4哪个更好,同质的,和上面的想法分析一样,将大问题划分为小问题2->(3,4)或者(2,3)->4

    参考代码

    #include<stdio.h>
    #include<string.h>
    #define Ma_x 99999
    #define Mi_x 0 
    #define min(a,b) a<b?a:b 
    #define max(a,b) a>b?a:b 
    int n,w[200],dp[200][200],dq[200][200];//n表示堆数,w表示每队的数量,dp[i][j]表示从第i堆开始合并j堆(包括第i堆)后的最小花费 ,dq表示最大 
    

    int sum(int i,int t){
    int sum=0,s1;
    for(int s=i;s<i+t;s++){
    s1 = s%n;
    if(s1==0)
    s1=n;
    sum=sum+w[s1];
    }
    return sum;
    }

    int main(){
    int i,t,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
    scanf("%d",&w[i]);
    dp[i][1]=0;//表示合并一堆的花费,没有合并则花费为0
    dq[i][1]=0;
    }
    //动态规划
    for(t=2;t<=n;t++){
    for(i=1;i<=n;i++){
    dp[i][t]=Ma_x;
    dq[i][t]=Mi_x;
    for(k=1;k<t;k++){
    dp[i][t]=min(dp[i][t],dp[i][k]+dp[(i+k-1)%n+1][t-k]+sum(i,t));
    dq[i][t]=max(dq[i][t],dq[i][k]+dq[(i+k-1)%n+1][t-k]+sum(i,t));
    }
    }
    }
    int mini=Ma_x;
    int maxi=Mi_x;
    for(i=1;i<=n;i++){//从第几堆石子开始结果最小
    mini=min(mini,dp[i][n]);
    maxi=max(maxi,dq[i][n]);
    }
    printf("%d “,mini);
    printf(”%d ",maxi);
    }

    个人博客空の城.

    展开全文
  • =100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20).(!)选择一种合并石子的方案,使用权...

    题目描述

    在一个圆形操场的四周摆放着N堆石子(N<=

    100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N及每堆栈的石子数(<=20).

    (!)选择一种合并石子的方案,使用权得做N-1次合并,得分的总和最小;

    (2)选择一种合并石子的方案,使用权得做N-1次合并,得分的总和最大;

    输入数据:

    第一行为石子堆数N;

    第二行为每堆的石子数,每两个数之间用一个空格分隔.

    输出数据:

    从第一至第N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案用N行表示,其中第i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可).要求将待合并的两堆石子数以相应的负数表示.

    输入输出范例:

    输入:

    4

    4 5 9 4

    输出:

    -4 5 9 -4

    -8 -5 9

    -13 -9

    22

    4 -5 -9 4

    4 -14 -4

    -4 -18

    22

    算法分析

    竞赛中多数选手都不约而同地采用了尽可能逼近目标的贪心法来逐次合并:从最上面

    的一堆开始,沿顺时针方向排成一个序列。 第一次选得分最小(最大)的相邻两堆合并,

    形成新的一堆;接下来,在N-1堆中选得分最小(最大)的相邻两堆合并……,依次类推,

    直至所有石子经N-1次合并后形成一堆。

    例如有6堆石子,每堆石子数(从最上面一堆数起,顺时针数)依次为3 46 5 4 2

    要求选择一种合并石子的方案,使得做5次合并,得分的总和最小。

    按照贪心法,合并的过程如下:

    每次合并得分

    第一次合并 3 4 6 5 4 2 5

    第二次合并 5 4 6 5 4 9

    第三次合并 9 6 5 4 9

    第四次合并 9 6 9 15

    第五次合并 15 9 24

    24

    总得分=5+9+9+15+24=62

    但是当我们仔细琢磨后,可得出另一个合并石子的方案:

    每次合并得分

    第一次合并 3 4 6 5 4 2 7

    第二次合并 7 6 5 4 2 13

    第三次合并 13 5 4 2 6

    第四次合并 13 5 6 11

    第五次合并 13 11 24

    24

    总得分=7+6+11+13+24=61

    显然,后者比贪心法得出的合并方案更优。 题目中的示例故意造成一个贪心法解题的

    假像,诱使读者进入“陷阱”。为了帮助读者从这个“陷阱”里走出来, 我们先来明确一

    个问题:

    1.最佳合并过程符合最佳原理

    使用贪心法至所以可能出错, 是因为每一次选择得分最小(最大)的相邻两堆合并,

    不一定保证余下的合并过程能导致最优解。聪明的读者马上会想到一种理想的假设:如果N

    -1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后

    的得分总和必然是最优的。

    例如上例中第五次合并石子数分别为13和11的相邻两堆。 这两堆石头分别由最初

    的第1,2,3堆(石头数分别为3,4,6)和第4,5,6堆(石头数分别为5,4,

    2)经4次合并后形成的。于是问题又归结为如何使得这两个子序列的N-2 次合并的得分

    总和最优。为了实现这一目标,我们将第1个序列又一分为二:第1、2堆构成子序列1,

    第3堆为子序列2。第一次合并子序列1中的两堆,得分7; 第二次再将之与子序列2的

    一堆合并,得分13。显然对于第1个子序列来说,这样的合并方案是最优的。同样,我

    们将第2个子序列也一分为二;第4堆为子序列1,第5,6堆构成子序列2。第三次合

    并子序列2中的2堆,得分6;第四次再将之与子序列1中的一堆合并,得分13。显然

    对于第二个子序列来说,这样的合并方案也是最优的。 由此得出一个结论──6堆石子经

    过这样的5次合并后,得分的总和最小。

    我们把每一次合并划分为阶段,当前阶段中计算出的得分和作为状态, 如何在前一次

    合并的基础上定义一个能使目前得分总和最大的合并方案作为一次决策。很显然,某阶段

    的状态给定后,则以后各阶段的决策不受这阶段以前各段状态的影响。 这种无后效性的性

    质符最佳原理,因此可以用动态规划的算法求解。

    2.动态规划的方向和初值的设定

    采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。 这些石子堆子序

    列包括:

    {第1堆、第2堆}、{第2堆、第3堆}、……、{第N堆、第1堆};

    {第1堆、第2堆、第3堆}、{第2堆、第3堆、第4堆}、……、{第N堆、第1

    堆、第2堆};

    ……

    {第1堆、……、第N堆}{第1堆、……、第N堆、第1堆}……{第N堆、第1堆、

    ……、第N-1堆}

    为了便于运算,我们用〔i,j〕表示一个从第i堆数起,顺时针数j堆时的子序列

    {第i堆、第i+1堆、……、第(i+j-1)mod n堆}

    它的最佳合并方案包括两个信息:

    ①在该子序列的各堆石子合并成一堆的过程中,各次合并得分的总和;

    ②形成最佳得分和的子序列1和子序列2。由于两个子序列是相邻的, 因此只需记住

    子序列1的堆数;

    f〔i,j〕──将子序列〔i,j〕中的j堆石子合并成一堆的最佳得分和;

    c〔i,j〕──将〔i,j〕一分为二,其中子序列1的堆数;

    (1≤i≤N,1≤j≤N)

    显然,对每一堆石子来说,它的

    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)。

    规划的方向是顺推。先考虑含二堆石子的N个子序列(各子序列分别从第1堆、第2堆、

    ……、第N堆数起,顺时针数2堆)的合并方案

    f〔1,2〕,f〔2,2〕,……,f〔N,2〕

    c〔1,2〕,c〔2,2〕,……,c〔N,2〕

    然后考虑含三堆石子的N个子序列(各子序列分别从第1堆、第2堆、……、第N堆

    数起,顺时针数3堆)的合并方案

    f〔1,3〕,f〔2,3〕,……,f〔N,3〕

    c〔1,3〕,c〔2,3〕,……,c〔N,3〕

    ……

    依次类推,直至考虑了含N堆石子的N个子序列(各子序列分别从第1堆、第2堆、 …

    …、第N堆数起,顺时针数N堆)的合并方案

    f〔1,N〕,f〔2,N〕,……,f〔N,N〕

    c〔1,N〕,c〔2,N〕,……,c〔N,N〕

    最后,在子序列〔1,N〕,〔2,N〕,……,〔N,N〕中,选择得分总和(f值)最

    小(或最大)的一个子序列〔i,N〕(1≤i≤N),由此出发倒推合并过程。

    3.动态规划方程和倒推合并过程

    对子序列〔i,j〕最后一次合并,其得分为第i堆数起,顺时针数j堆的石子总数t。被

    合并的两堆石子是由子序列〔i,k〕和〔(i+k-1)modn+1,j-k〕(1≤k≤j-1)

    经有限次合并形成的。为了求出最佳合并方案中的k值,我们定义一个动态规划方程:

    当求最大得分总和时

    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堆的堆序号。

    例如对(图6.2-4)中的6堆石子,按动态规划方程顺推最小得分和。 依次得出含

    二堆石子的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个子序列的合并方案

    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个子序列的合并方案

    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个子序列的合并方案

    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个子序列的合并方案

    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

    上述倒推过程,可由一个print(〔子序列〕)的递归算法描述

    procedure print (〔i,j〕)

    begin

    if j〈〉1 then {继续倒推合并过程

    begin

    print(〔i,c〔i,j〕);{倒推子序列1的合并过程}

    print(〔i+c〔i,j〕-1)mod n+1,j-c〔i,j〕)

    {倒推子序列2的合并过程}

    for K:=1 to N do{输出当前被合并的两堆石子}

    if (第K堆石子未从圈内去除)

    then begin

    if(K=i)or(K=X)then置第K堆石子待合并标志

    else第K堆石子未被合并;

    end;{then}

    第i堆石子数←第i堆石子数+第X堆石子数;

    将第X堆石子从圈内去除;

    end;{then}

    end;{print}

    例如,调用print(〔1,6〕)后的结果如下:

    print(〔1,6〕)⑤

    ┌──────┴──────┐

    │ │

    print(〔1,3〕)② print(〔4,3〕)④

    │ │

    print(〔1,2〕)① ┌─────┴─────┐

    │ │ │

    ┌─────┴─────┐ print(〔4,1〕) print(〔5,2〕)③

    │ │ │

    print(〔1,1〕) print(〔2,1〕) │

    ┌──────┴──────┐

    │ │

    print(〔5,1〕) print(〔6,1〕)

    (图6.2-5)

    其中回溯至

    ① 显示 3 46 5 4

    ② 显示 7 65 4 2

    ③ 显示 13 54 2

    ④ 显示 135 6

    ⑤ 显示 13 11

    注:调用print过程后,应显示6堆石子的总数作为第5次合并的得分。

    代码:【c语言】

    #include

    #include

    #include

    #define max 100

    int a[max],m[max][max],f[max][max];

    int n;

    FILE *fp;

    int add(int x)

    {

    if(x!=n)

    return ++x;

    return 1;

    }

    int see(int x)

    {

    if(x%n==0)

    return

    n;

    return (x%n);

    }

    void input()

    {

    int i,j,k,temp=0;

    fp=fopen("input.txt","r");

    if(fp==NULL)

    exit(0);

    fscanf(fp,"%d",&n);

    for(i=1;i<=n;i++)

    fscanf(fp,"%d",&a[i]);

    for(i=1;i<=n;i++)

    for(j=1;j<=n;j++)

    {

    k=i;

    while(k!=j)

    {

    temp+=a[k];

    k=add(k); }

    temp+=a[k];

    m[i][j]=temp;

    temp=0;

    }

    fclose(fp);

    }

    int fun(int i,int j)

    {

    if(i==j)

    return

    0;

    if(see(i+1)==j)

    return

    m[i][j];

    int min,k,temp;

    k=i;

    while(k!=j)

    {

    if(k==i)

    {

    min=f[i][k]+f[add(k)][j]+m[i][k]+m[add(k)][j];

    k=add(k);

    continue; }

    temp=f[i][k]+f[add(k)][j]+m[i][k]+m[add(k)][j];

    if(temp

    min=temp;

    k=add(k);

    }

    return min;

    }

    main()

    {

    input();

    int i,j,min,temp,t;

    for(temp=1;temp<=n;temp++)

    for(i=1,j=temp;i<=n;i++)

    {

    f[i][see(j)]=fun(i,see(j));

    j=add(j);

    }

    min=f[1][n];

    for(i=2;i<=n;i++)

    {

    if(f[i][i-1]

    min=f[i][i-1];

    }

    printf("%d",min);

    getch();

    }

    展开全文
  • 动态规划之合并石子

    千次阅读 多人点赞 2020-08-17 21:40:43
    动态规划——合并石子C语言解) 第一次接触到动态规划是在斐波那契数列,那个时候还不知道动态规划的概念,由于数据量较小,直接用for循环就通过了,直到遇到了”合并石子“这道题目,百度过很多的文章都没看懂,...
  • C++-石子合并问题

    2021-10-20 19:22:13
    规定每次只能选择相邻的两堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 算法设计:试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 思路: 最小值是总是最小的两个数相加,...
  • c语言练习动态规划/贪心之石子合并

    千次阅读 2020-04-07 22:31:38
    石子合并 有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆,规定每次只能选相邻的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分,编一程序,给出堆数n及每堆石子数(<=200); (1)...
  • 在空地上,有n堆石子排成一排,你需要把这些石子合并成一堆石子。你每次只能合并 相邻的两堆石子。而将两堆石子合并的代价是这两堆石子的个数之和。 在开始合并前,你可以有一次机会去交换某相邻的两堆石子。
  • 动态规划算法是计算机算法设计中的一个重要算法,通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推的方式去解决,石子合并问题作为典型算例,能够彰显动态规划算法特征 针对石子合并问题,本文利用...
  • 本文主要内容: 1. 问题描述 2. 输入输出示例 3. 算法设计思想与算法描述 ...合并的过程只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和,经过N-1次合并后成为一堆。求出总的代价最小值。
  • 题目 在一个圆形操场的四周摆放着n堆石子。...我们知道链式的石子合并问题是相邻两堆之间可以合并,那么环形的和链式的区别就在于,环形的相当于是链式的头尾两堆也能合并 那么,我们只要解决,如何在链式的基础上.
  • 动态规划——石子合并问题

    千次阅读 多人点赞 2020-02-05 23:20:10
    石子合并问题分三类: 1、任意合并 2、相邻的才能合并且排成直线 3、相邻的才能合并且围成圈 1、贪心即可解决 2、直线型 合并石子直线型 对于区间dp问题,我们先要把它细分为区间 我们可以这样定义dp数组 dp[i][j]的...
  • 1.石子合并问题 在一个圆形操场的四周摆放着n堆石子。现要将石子有序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。设计一个算法,计算出将n堆石子合并成一堆的...
  • 石子合并问题代码

    2013-05-31 01:19:00
    算法分析课程作业,C语言编写,可能需要用input.txt输入,石子合并问题代码
  • 动态规划之石子合并问题(Circle版)

    千次阅读 多人点赞 2020-05-22 23:22:40
    这个问题和普通的石子合并问题不同,简单的石子合并问题采用的是将石子线性排列并合并,但是这个问题要求石子按照圆圈排列,所以首尾两个石子是能够合并的。 这就不由得引起我们的思考,我们怎么才能让首尾也相邻呢?...
  • C++石子合并问题(动态规划)

    万次阅读 多人点赞 2018-06-25 10:55:54
    规定每次只能选择相邻的两堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 算法设计:试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 样例输入:由input.txt提供输入数据 样例...
  • 合并石子(动态规划经典题)

    千次阅读 2017-08-03 00:19:46
    1. 设状态:f[i][j]表示从第i堆合并到第j堆,合并成一堆的最小得分 2. 初始状态:f[i][i]=0;  最终状态:f[1][n];//从第1堆合并到第n堆的最小得分 3.状态转移方程:f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i...
  • 一.问题描述 在一条直线上有n堆石子, 要求每次将相邻的两堆石子合成一堆,花费=两堆石子的总数 求最省总花费. ...//石子合并问题(直线型) 一条直线上只有相邻的石子堆可以合并.合并i堆和j堆的花...
  • 石子归并问题(区间dp)

    2016-10-19 00:41:14
    区间dp,顾名思义就是在区间上进行的一系列动态规划。 1.51nod1021石子归并问题 ...problemId=1021 ...规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一
  • =100),现要将石子有次序地合并成一堆,规定每次只能选相邻的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分,编一程序,给出堆数n及每堆石子数(<=200); (1)选择一种合并石子的方案,使得做n-1次...
  • 石子合并问题(动态规划)

    千次阅读 多人点赞 2020-06-10 09:44:03
    =100),现要将石子有次序地合并成一堆,规定每次只能选相邻的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分,编一程序,给出堆数n及每堆石子数(<=200); (1)选择一种合并石子的方案,使得做n-1次...
  • 有n堆石子排成一排,每堆石子有一定的数量,现要将n堆石子合并成为一堆,合并只能每次将相邻的两堆石子堆成一堆,每次合并花费的代价为这两堆石子的和, 经过n-1次合并后成为一堆,求出总代价的最小值。 输入描述:有...
  • 详解动态规划石子合并问题(直线型, 环形)

    千次阅读 多人点赞 2019-04-05 10:39:34
    试设计出1个算法,计算出将N堆石子合并成1堆的最小花费和最大花费. 输入输出格式 输入格式: 数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数. 输入示例 4 4 4 5 9 输出示例 43 ...
  • 石子合并问题

    2020-09-20 09:00:21
    1. 线性(相邻)合并问题 题目描述: 一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 请编辑计算出将n堆石子合并...
  • 规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 试设计一个算法。 选择一种合并石子的方案,使得做 n-1次合并得分总和最大。 选择一种合并石子的方案,使得做 n−1 次合并...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 274
精华内容 109
关键字:

c语言石子合并问题