您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

石子合并问题的求解

开始以为通过贪心算法可能很快解决问题,可却是行不通的。首先我们可以把这么堆石子看成一列,我们假如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

由此我们知道本题是不可以使用贪心法求解的,上例中第五次合并石子数分别为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堆,得分2;第四次再将之与子序列1中的一堆合并,得分13。显然对于第二个子序列来说,这样的合并方案也是最优的。由此得出一个结论──6堆石子经过这样的5次合并后,得分的总和最小。

举例:拆环成链后得到  4 5 9 4

首先,当成一条链来做,那么最后一次合并,也就是所有的石子合并成一堆的时候,我们得到的结果是 4+5+9+4

最后一次合并一定是两堆石子合并,关键是这两堆石子有可能的是:

第1种可能性:(4),(5,9,4),4是一堆石子,(5,9,4)合并的一堆石子

第2种可能性:(4,5),(9,4)

第3种可能性:(4,5,9),(4)

所以,我们需要更加抽象一点来思考,设f(i,j)表示第i堆石子到第j堆石子合并成一堆石子的最大得分,sum(i,j)表示第i到第j的和:

f(i,j) = max{f(i,k)+f(k+1,j)} +sum(i,j), i<=k <j,k表示把i和j从中间分开,边界f[i][i] = 0

所以一条链的石子合并就OK了,关键环形的怎么做。

最简单的想法是从环形的每一个点拆成多条链,分别求每条链的最大值,然后从这些最大值中找一个最大的,就是答案,例如样例数据可以写成:4 5 9 4 5 9 4 4 9 4 4 5 4 4 5 9,可以写成4条链。

但是如果这样拆环,我们就会发现,我们重复的计算了一些数据:

4 [5 9 4] [5 9 4] 4 9 4 4 5 4 4 5 9

我们重复计算了(4,5,9) 合并的一堆石子的最大值。

所以应该这样拆环成链:4 5 9 4 4 5 9

包含了上面的所有的链,我们要求的是f(1,4) ==>4 5 9 4 ;f(2,5) ==>5 9 4 4 ;f(3,6) ==>9 4 4 5 ;f(4,7) ==>4 4 5 9。这样做的好处是:不会导致重复计算。

因为要先计算:f(1,2),f(2,3),f(3,4),f(4,5),f(5,6),f(6,7),长度为2,

再计算:f(1,3),f(2,4),f(3,5),f(4,6),f(5,7) 长度为3,

最后计算:f(1,4),f(2,5),f(3,6),f(4,7) 长度为4

边界:f(i,i) = 0

以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件,必须遵循软件工程的原则,设计出高效率的程序。一个高效的程序不仅需要编程技巧,更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家认为,算法是一种创造性思维活动,并且处于计算机科学与技术学科的核心。


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进