アルゴリズムjava実現--遡及法--バッチ処理作業スケジュール問題

1570 ワード

作業スケジュール問題を一括処理するjava実現(遡及法)
具体的な問題の説明とC/C++はURLを参照することを実現します。
http://blog.csdn.net/liufeng_king/articale/detail/8764319
/**
 *          --   (   )
 * @author Administrator
 *
 */
public class FlowShop {
	 int n;//   
	 int f1;//  1      
	 int f;//     
	 int bestf;//     
	 int[][] m;//          
	 int []x;//      
	 int[] bestx;//        
	 int[] f2;//  2      
	public FlowShop(int n,int[][] m){
		this.n=n;
		this.m=m;
		f1=0;
		f=0;
		bestf=10000;//     
		bestx=new int[n+1];
		x=new int[n+1];
		//   ,x[i]     
		for(int i=1;i<=n;i++){
			x[i]=i;
		}
		f2=new int[n+1];
	}
	public  void swap(int[] x,int i,int j){
		int temp=x[i];
		x[i]=x[j];
		x[j]=temp;
	}

	public  void backtrack(int i){
		if(i>n){
			for(int j=1;j<=n;j++)
				bestx[j]=x[j];
			bestf=f;
		}
		else{
			for(int j=i;j<=n;j++){
				f1+=m[x[j]][1];//  x[j]         
				f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+m[x[j]][2];//f2[i]  f2[i-1] f1        x[j]  2      
				f+=f2[i];
				if(f<bestf){
					swap(x,i,j);
					backtrack(i+1);
					swap(x,i,j);
				}
				f1-=m[x[j]][1];
				f-=f2[i];
			}
		}
	}
	public static void main(String[] args) {
		int n=3;
		int[][] m={{0,0,0},{0,2,1},{0,3,1},{0,2,3}};//m    1  ,      0        0  
		FlowShop f=new FlowShop(n,m);
		f.backtrack(1);
		System.out.println("            :");
		for(int i=1;i<=n;i++)
			System.out.print(f.bestx[i]+" ");
		System.out.println();
		System.out.println("            :"+f.bestf);
	}
}
/*
     :
 
             :
1 3 2 
            :18
 */