アルゴリズムjava実現--遡及法--バッチ処理作業スケジュール問題
1570 ワード
作業スケジュール問題を一括処理するjava実現(遡及法)
具体的な問題の説明とC/C++はURLを参照することを実現します。
http://blog.csdn.net/liufeng_king/articale/detail/8764319
具体的な問題の説明と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
*/