一 问题分析
二 代码实现
package MatrixChain;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
class matrixChain
{
int []p; //各个矩阵的规模 有效起始位置为0
int [][]m; //各个长度的最优解 0 1 2
int [][]s; //各个长度的最优断开位置
public matrixChain(int []p)
{
this.p=p;
m=new int[p.length][p.length];
s=new int[p.length][p.length];
MatrixChain();
traceBack(1,p.length-1);
display();
}
public void MatrixChain()
{
for(int i=1; i<p.length; i++)
{
m[i][i]=0; //长度为零的情况
}
for(int l=1; l<p.length-1; l++) //以l为变量遍历所有可能
{
for(int i=1; i<p.length-l; i++)
{
int j=i+l;
//以i为断点
m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1; k<j; k++)
{
int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
if(m[i][j]>temp)
{
m[i][j]=temp;
s[i][j]=k;
}
}
}
}
}
public void traceBack(int i, int j)
{
if(i+1<j)
{ //中序遍历
int k=s[i][j];
System.out.println("断开位置: "+k);
traceBack( i, k);
traceBack( k+1, j);
}
}
public void display()
{
try
{
BufferedWriter fout=new BufferedWriter(new FileWriter("out.txt"));
fout.write("m[j][j]");
fout.newLine();
for(int i=1; i<p.length; i++)
{
for(int j=1; j<p.length; j++)
{
fout.write(""+m[i][j]+" ");
}
fout.newLine();
}
fout.flush();
fout.write("s[j][j]");
fout.newLine();
for(int i=1; i<p.length; i++)
{
for(int j=1; j<p.length; j++)
{
fout.write(""+s[i][j]+" ");
}
fout.newLine();
}
fout.flush();
} catch (IOException e)
{
e.printStackTrace();
}
}
}
public class bin
{
public static void main(String[] args)
{
int []p={30,35,15,5,10,20,25};
matrixChain myMatrixChain=new matrixChain(p);
}
}
三 运行结果
m[j][j]
0 15750 7875 9375 11875 15125
0 0 2625 4375 7125 10500
0 0 0 750 2500 5375
0 0 0 0 1000 3500
0 0 0 0 0 5000
0 0 0 0 0 0
s[j][j]
0 1 1 3 3 3
0 0 2 3 3 3
0 0 0 3 3 3
0 0 0 0 4 5
0 0 0 0 0 5
0 0 0 0 0 0
断开位置
3
1
5