matrixchain.java

《算法设计与分析》王晓东编著

import java.util.*;
public class MatrixChain {

	/**
	 * @param args
	 */

	                    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		System.out.print("Please input the number of matrices  n =");
		int n = in.nextInt();
		int[][] m = new int[n][n];
		int[][] s = new int[n][n];
		int[] p = new int[n+1];
		System.out.print("Please input the dimensions:\n");
		for(int i=0;i<=n;i++){
			System.out.print("p"+i+" = ");
			p[i] = in.nextInt();
		}
		matrixChain(p,m,s);
		for(int i=0;i<=n;i++)
			System.out.print(p[i]+"\t");
		System.out.println();
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				System.out.print(m[i][j]+"\t");
			}
			System.out.println();
		}
		System.out.println("s[i][j]");
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				System.out.print(s[i][j]+"\t");
			}
			System.out.println();
		}
		traceback(s,0,n-1);
	}
	public static void  matrixChain(int[] p,int[][] m,int[][] s){
		int n = p.length-1;
		for(int i=0;i<n;i++)	{m[i][i] = 0;s[i][i] = 0;}
		for(int l=1;l<n;l++){
			for(int i=0;i+l<n;i++)
			{	int min = -1;
				int temp = 0;
				for(int k=i;k<i+l;k++){
					if(min == -1){
						min = m[i][k]+m[k+1][i+l]+p[i]*p[k+1]*p[i+l+1];
						s[i][i+l] = k;
					}
					else{
						temp=m[i][k]+m[k+1][i+l]+p[i]*p[k+1]*p[i+l+1];
						if(temp<min){min=temp;s[i][i+l]=k;}
					}
				}
				m[i][i+l] = min;
			}
		}
				
	}
	public static void traceback(int[][] s,int i,int j){
		if(i==j) return;
		traceback(s,i,s[i][j]);
		traceback(s,s[i][j]+1,j);
		System.out.println("Multiplay A"+i+","+s[i][j]+"and A"+
				(s[i][j]+1)+","+j);
	}
}