設有n件作業分配給n個人，將作業i分配給第j個人所需的費用為cij ， 設計一個演算法，對于給定的作業費用，為每一個人都分配1 件不同的作業，并使總費用達到最小，
輸入格式:
輸入資料的第一行有1 個正整數n (1≤n≤20)，接下來的n行，每行n個數，表示作業費用，
輸出格式:
將計算出的最小總費用輸出到螢屏，
輸入樣例:
在這里給出一組輸入，例如：
3
10 2 3
2 3 4
3 4 5
輸出樣例:
在這里給出相應的輸出，例如：
9
這里同樣采用回溯法，以物品為順序來選擇被安排的工人；其中陣列a[][]的第一列留為標記位，用來判斷工人是否被安排作業；通過判斷當前花費總時間是否仍小于最小值min來剪枝；具體代碼如下：
package 宿題; import java.io.*; public class Main { static int a[][]; static int n; static int min=Integer.MAX_VALUE; public static void main(String args[])throws IOException{ StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); n=(int)in.nval; a=new int[n+1][n+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ in.nextToken(); a[i][j]=(int)in.nval; } } Arrange(a,1,0); System.out.println(min);//輸出最小值； } private static void Arrange(int a[][],int i,int sum){ if(i>n){//到達最后節點，比較最小值； if(sum<min) min=sum; }else{ for(int I=1;I<=n;I++){//分為和當前未分配工人數目一致個數的子結點； if(a[I][0]!=-1){//判斷當前工人是否被分配作業； a[I][0]=-1;//將當前未分配工人標記位改為-1，并進入子結點； if(sum+a[I][i]<min)//判斷子結點是否可能存在解，否則減去； Arrange(a,i+1,sum+a[I][i]); a[I][0]=0;//還原標記位，使其不影響相鄰結點； } } } } } 該演算法最壞情況的時間復雜度為O(2^n)，轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121142.html
標籤：其他
上一篇：7-1 0-1背包 (20 分)