fac3_10.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 98 页，例
//最优二叉搜索树问题动态规划解法

 public class Fac3_10{   
   public static void optimalBinarySearchTree(float []a,float []b,float[][] m,
                                                 int [][]s,float[][] w)
   {
     int n=a.length-1;
     for(int i=0;i<=n;i++){
        w[i+1][i]=a[i];
        m[i+1][i]=0;
       }       
     for(int r=0;r<n;r++)
      for(int i=1;i<=n-r;i++){
        int j=i+r;
        w[i][j]=w[i][j-1]+a[j]+b[j];
        m[i][j]=m[i+1][j];
        s[i][j]=i;
        for(int k=i+1;k<=j;k++) {
          float t=m[i][k-1]+m[k+1][j];
          if(t<m[i][j]){
           m[i][j]=t;
           s[i][j]=k;
          }
        m[i][j]+=w[i][j];
        }
      }
   }
           

      public static void main(String args[])
  {
    float a1[]={0.02f,0.02f,0.02f,0.02f,0.02f,0.02f};
    float b1[]={0.0f,0.14f,0.2f,0.2f,0.2f,0.14f};
    int n1=a1.length;  
    int n2=b1.length;
    float m1[][]=new float[n1+1][n2+1] ;    
    int s1[][]=new int[n1+1][n2+1];
    float [][]w1=new float[n1+1][n2+1];
    optimalBinarySearchTree(a1,b1,m1,s1,w1);
    System.out.println("输出二叉最优搜索树根结点元素  ");
    for(int i=1;i<n1;i++){
     for(int j=1;j<n2;j++)
    System.out.print(s1[i][j]+"  ");
    System.out.println();
   }
  }
}