matrixdynamicmulti.java

用动态规划实现矩阵链乘的java代码

import java.util.*;
import java.io.*;
class MatrixDynamicMulti 
{
	public static void matrixChain(int[] p,int n,int [][]m,int [][]s) throws Exception{
		for(int i=0;i<n;i++) m[i][i]=0;
		for(int r=1;r<n;r++)
			for(int i=0;i<n-r;i++){
				int j=i+r-1;
				m[i+1][j]=m[i+1][j]+p[i]*p[i+1]*p[j];
				s[i][j]=i;
				for(int k=i;k<j-1;k++){
					int t=m[i][k]+m[k+1][j]+p[i]*p[k]*p[j];
					if(t<m[i][j]){
						m[i][j]=t;
						s[i][j]=k;
					}
				}
		}
	}

	public static void traceback(int [][]s,int i,int j){
		if(i==j) return;
		traceback(s,i-1,s[i-1][--j]);
		traceback(s,s[i][j]+1,j);
		System.out.println("Multiply A: "+i+","+s[i][j]+" and M "+(s[i][j]+1)+","+j);
	}

	public static void main(String[] args) throws Exception{
		int num;
		System.out.print("请输入矩阵的个数：");
		BufferedReader br=new BufferedReader(
									new InputStreamReader(System.in));
		 num=Integer.parseInt(br.readLine());
		Random rand=new Random();
		int []row_col=new int[num+1];
		for(int i=0;i<=num;i++){
			row_col[i]=rand.nextInt(8);
			if(row_col[i]==0){
				i--;
				continue;
			}
			System.out.print(row_col[i]+"\t");
		}
		System.out.println();

		for(int i=0;i<row_col.length-1;i++)
			System.out.println("第"+(i+1)+"个矩阵的行列数为："+row_col[i]+"*"+row_col[i+1]);

		int [][]mm=new int[num][];
		for(int i=0;i<num;i++)
			mm[i]=new int[num];
		int [][]ss=new int[num][];
		for(int i=0;i<num;i++)
			ss[i]=new int[num];

		matrixChain(row_col,num,mm,ss);
		traceback(ss,1,num);
		System.out.println(mm[0][num-1]);
	}
};