注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!

Pascal经典算法详解 – 石子合并问题

其他 水墨上仙 2248次浏览 已收录 手机上查看

石子合并】 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。 试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。 【输入文件】 包含两行,第1 行是正整数n(1<=n<=100),表示有n堆石子。 第2行有n个数,分别表示每堆石子的个数。
【输出文件】 输出两行。 第1 行中的数是最小得分;第2 行中的数是最大得分。
【输入样例】44 4 5 9
【输出样例】4354
【分析】     本题初看以为可以使用贪心法解决问题,但是事实上因为有必须相邻两堆才能合并这个条件在,用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。
例如下面这个例子:    6    3 4 6 5 4 2    如果使用贪心法求最小得分,应该是如下的合并步骤:        
第一次合并 3 4 6 5 4 2    2,3合并得分是5       
 第二次合并 5 4 6 5 4      5,4合并得分是9        
第三次合并 9 6 5 4        5,4合并得分是9     
 第四次合并 9 6 9          9,6合并得分是15        
第五次合并 15 9           15,9合并得分是24        
总得分=5+9+9+15+24=62   
 但是如果采用如下合并方法,却可以得到比上面得分更少的方法:        
第一次合并 3 4 6 5 4 2     3,4合并得分是7        
第二次合并 7 6 5 4 2       7,6合并得分是13        
第三次合并 13 5 4 2        4,2合并得分是6        
第四次合并 13 5 6          5,6合并得分是11        
第五次合并 13 11           13,11合并得分是24        
总得分=7+13+6+11+24=61    由此我们知道本题是不可以使用贪心法求解的,上例中第五次合并石子数分别为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次合并后,得分的总和最小。     
动态规划思路:    
阶段i:石子的每一次合并过程,先两两合并,再三三合并,…最后N堆合并    状态s:每一阶段中各个不同合并方法的石子合并总得分。  
 决策:把当前阶段的合并方法细分成前一阶段已计算出的方法,选择其中的最优方案    具体来说我们应该定义一个数组s[i,j]用来表示合并方法,i表示从编号为i的石头开始合并,j表示从i开始数j堆进行合并,s[i,j]为合并的最优得分。  

  对于上面的例子来说,初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1],因为一开始还没有合并,所以这些值应该全部为0。    第二阶段:两两合并过程如下,其中sum(i,j)表示从i开始数j个数的和            
 s[1,2]=s[1,1]+s[2,1]+sum(1,2)             
 s[2,2]=s[2,1]+s[3,1]+sum(2,2)              
s[3,2]=s[3,1]+s[4,1]+sum(3,2)            
  s[4,2]=s[4,1]+s[5,1]+sum(4,2)            
  s[5,2]=s[5,1]+s[6,1]+sum(5,2)             
 s[6,2]=s[6,1]+s[1,1]+sum(6,2)    
第三阶段:三三合并可以拆成两两合并,拆分方法有两种,前两个为一组或后两个为一组       
  s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3),取其最优        
 s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3),取其最优                             .                             .                             .    第四阶段:四四合并的拆分方法用三种,同理求出三种分法的得分,取其最优即可。
以后第五阶段、第六阶段依次类推,最后在第六阶段中找出最优答案即可。   
 由此得到算法框架如下:    For j←2 to n do    {枚举阶段,从两两合并开始计算}    
  For i←1 to n do   {计算当前阶段的n种不同状态的值}     
    For k←1 to j-1 do {枚举不同的分段方法}          
 begin           
  If i+k>n then t←(i+k) mod n else t←i+k {
最后一个连第一个的情况处理
}            
 s[i,j]←最优{s[i,k]+s[t,j-k]+sum[1,3]} {sum[i,j]表示从i开始数j个数的和}
【参考程序】

var
 n:integer;
 a:array[1..100] of longint;
 s:array[1..100,1..100] of longint;
 t:array[0..100,0..100] of longint;
 i,j,k,temp,max,min:longint;
begin
 assign(input,'shizi.in');
 reset(input);
 readln(n);
 fillchar(t,sizeof(t),0); {计算和数组}
 for i:=1 to n do
 read(a[i]);
 for i:=1 to n do
 for j:=1 to n do
 for k:=i to i+j-1 do
 begin
 if k>n then temp:=k mod n else temp:=k;
 t[i,j]:=t[i,j]+a[temp];
 end;
{动态规划求最大得分}
 fillchar(s,sizeof(s),0);
 for j:=2 to n do
 for i:=1 to n do
 for k:=1 to j-1 do
 begin
 if i+k>n then temp:=(i+k) mod n else temp:=i+k; {处理环形问题}
 max:=s[i,k]+s[temp,j-k]+t[i,j];
 if s[i,j]<max then s[i,j]:=max;
 end;
 max:=0; {在最后的阶段状态中找最大得分}
 for i:=1 to n do
 if max<s[i,n] then max:=s[i,n];
{动态规划求最小得分}
 fillchar(s,sizeof(s),0);
 for j:=2 to n do
 for i:=1 to n do
 begin
 min:=maxlongint;
 for k:=1 to j-1 do
 begin
 if i+k>n then temp:=(i+k) mod n else temp:=i+k; {处理环形问题}
 s[i,j]:=s[i,k]+s[temp,j-k]+t[i,j];
 if min>s[i,j] then min:=s[i,j];
 end;
 s[i,j]:=min;
 end;
 min:=maxlongint; {在最后的阶段状态中找最小得分}
 for i:=1 to n do
 if min>s[i,n] then min:=s[i,n];
 writeln(max);
 writeln(min);
end.


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Pascal经典算法详解 – 石子合并问题
喜欢 (0)
[开心洋葱]
分享 (0)
水墨上仙
关于作者:
水墨上仙
加载中……