////本程序取自王曉東編著“算法分析與設計”第 182 頁，例//電路板排列問題回溯解法     class Board{     static int n;         //電路板數     static int m;         //連接塊數     static int[] x;       //當前解     static int[] bestx;   //當前最優解     static int[] total;   //total[j]=連接塊j的電路板數     static int[] now;     //now[j]=當前解中所含連接塊j的電路板數     static int bestd;     //當前最優密度     static int[][] b;     //連接塊數組   public static int arrange(int[][] bb,int mm,int[] xx)    {    //初始化       n=bb.length-1;       m=mm;       x=new int[n+1];       bestx=xx;       total=new int[m+1];       now= new  int[m+1];       bestd=m+1;       b=bb; //置x為單位排列      for (int i=1; i<=n; i++)        {  x[i]= i;      for (int j=1; j<=m; j++)          total[j]+=b[i][j];        }//回溯搜索        backtrack(1,0);        return bestd;    }  static void swap(int[] a,int i,int j)    {       int temp;       temp=a[i];       a[i]=a[j];       a[j]=temp;    }  private static void backtrack(int i,int dd)    {     if(i==n)     {      for(int j=1;j<=n;j++)        bestx[j]=x[j];      bestd=dd;     }     else      for(int j=i;j<=n;j++)     {//選擇x[j]為下一塊電路板       int d=0;       for(int k=1;k<=m;k++)        {         now[k]+=b[x[j]][k];         if(now[k]>0 && total[k]!=now[k])d++;        }  //更新d值    if(dd>d)d=dd;   //System.out.println("d="+d+" dd="+dd+"  bestd="+bestd);    if(d<bestd)        {//搜索子樹       swap(x,i,j);       backtrack(i+1,d);       swap(x,i,j);        }        //恢復狀態    for(int k=1;k<=m;k++)      now[k]-=b[x[j]][k];     }   } }  public class Fac5_11{    public static void main(String args[])     {       int n1=8;       int m1=5;       int nm=0;       int [][]bt=new int[n1+1][m1+1];       int []x1=new int[n1+1];       bt[1][1]=0;bt[1][2]=0;bt[1][3]=0;bt[1][4]=0;bt[1][5]=0;       bt[2][1]=0;bt[2][2]=1;bt[2][3]=1;bt[2][4]=0;bt[2][5]=0;       bt[3][1]=0;bt[3][2]=1;bt[3][3]=1;bt[3][4]=1;bt[3][5]=0;       bt[4][1]=1;bt[4][2]=0;bt[4][3]=0;bt[4][4]=0;bt[4][5]=0;       bt[5][1]=1;bt[5][2]=0;bt[5][3]=0;bt[5][4]=0;bt[5][5]=0;       bt[6][1]=1;bt[6][2]=0;bt[6][3]=0;bt[6][4]=1;bt[6][5]=0;       bt[7][1]=0;bt[7][2]=0;bt[7][3]=0;bt[7][4]=0;bt[7][5]=1;       bt[8][1]=0;bt[8][2]=0;bt[8][3]=0;bt[8][4]=0;bt[8][5]=1;       Board aa=new Board();       nm=aa.arrange(bt,m1,x1);       System.out.println("密度  "+nm);       System.out.println("電路板最佳排列順序  ");       for(int i=1;i<=n1;i++)       System.out.print("  "+aa.bestx[i]);       System.out.println("  ");     } }