/**//*【石子合并】
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
*/
/**//*
分析】
本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子：
6
3 4 6 5 4 2
如果使用贪心法求最小得分，应该是如下的合并步骤：
第一次合并 3 4 6 5 4 2 2,3合并得分是５
第二次合并 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
由于不能用贪心算法解题我们用动态规划的方法解决问题：
阶段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[2,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[i,j]} {sum[i,j]表示从i开始数j个数的和}
end;
*/
public class CircleStone
{
public void maxStone(int[] a)
{
int n=a.length;
int[][] s=new int[a.length][a.length+1];
for(int j=2;j<=n;j++)
for(int i=0;i<n;i++)
{
s[i][j]=s[i][1]+s[(i+1)%n][j-1]+sum(a,i,j);
for(int k=2;k<=j-1;k++)
{
int t=(i+k)%n;
int temp=s[i][k]+s[t][j-k]+sum(a,i,j);
if(s[i][j]<temp)
{
s[i][j]=temp;
}
}
}
int temp=s[0][n];
for(int i=1;i<n;i++)
{
if(s[i][n]>temp)
temp=s[i][n];
}
System.out.println("Max="+temp);
}
public void minStone(int[] a)
{
int n=a.length;
int[][] s=new int[a.length][a.length+1];
for(int j=2;j<=n;j++)
for(int i=0;i<n;i++)
{
s[i][j]=s[i][1]+s[(i+1)%n][j-1]+sum(a,i,j);
for(int k=2;k<=j-1;k++)
{
int t=(i+k)%n;
int temp=s[i][k]+s[t][j-k]+sum(a,i,j);
if(s[i][j]>temp)
{
s[i][j]=temp;
}
}
}
int temp=s[0][n];
for(int i=1;i<n;i++)
{
if(s[i][n]<temp)
temp=s[i][n];
}
System.out.println("Min="+temp);
}
public int sum(int[] a,int i,int j)
{
int sum=0;
int length=a.length;
for(int k=i;k<i+j;k++)
{
int t=k;
if(k>length-1) t=t%length;
sum+=a[t];
}
return sum;
}
public static void main(String[] args)
{
int[] a={3,4,6,5,4,2};
CircleStone cs=new CircleStone();
cs.maxStone(a);
cs.minStone(a);
}
}
posted on 2008-06-28 18:24
夏日清风 阅读(2377)
评论(0) 编辑 收藏