fac3_7.java

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

//本程序取自王晓东编著“算法分析与设计”第 85 页，例
//电路布线问题动态规划解法
public class Fac3_7{
   public static void mnset(int[] c,int[][] size)
   {
     int n=c.length-1;
     for(int j=0;j<c[1];j++)
        size[1][j]=0;
     for(int j=c[1];j<=n;j++)
        size[1][j]=1; 
     for(int i=2;i<n;i++){
      for(int j=0;j<c[i];j++)
        size[i][j]=size[i-1][j];
      for(int j=c[i];j<=n;j++)
        size[i][j]=Math.max(size[i-1][j],size[i-1][c[i]-1]+1); 
      }
     size[n][n]=Math.max(size[n-1][n],size[n-1][c[n]-1]+1); 
   }     
           
  public static int traceback(int[] c,int[][] size,int[] net)
  { 
    int n=c.length-1;
    int j=n;
    int m=0;
    for(int i=n;i>1;i--)
      if(size[i][j]!=size[i-1][j]){
      net[m++]=i;
      j=c[i]-1; }
      if(j>=c[1])
        net[m++]=1;
    return m;
  }

  public static void main(String args[])
  {
  //c[i]存储i连线对应点号,必须注意在输入点前增加一个0，以确定1点时的空集
  // size[i][j]表示函数Size(i,j)的值
  //net[0:m-1]存储MNS(n,n)中的m条连线
    int  v1[]={0,8,7,4,2,5,1,9,3,10,6};
    int  n1=v1.length-1;
    int  v2[]=new int[n1+1];
    int [][]m1=new int[n1+1][n1+1];
    mnset(v1,m1);
    int m=traceback(v1,m1,v2);
    System.out.println("输出最大不相交线号");
     for(int i=0;i<m;i++)
     System.out.print("("+(v2[i])+","+v1[v2[i]]+")  ");
    System.out.println();
  }
}