动态规划之装配线调度

参考资料：《算法导论第二版第15章》

代码有注释，参考注释应该能够看明白

public class assemblyline {public static void main(String[] args) {int n =6;//每条线上装配站的个数int[][] a ={{7,9,3,4,8,4},{8,5,6,4,5,7}};//装配站Si，j上所需要的装配时间为a[i,j]int[][] t ={{2,3,1,3,4},{2,1,2,2,1}};//把已经通过装配站si，j的底盘从装配线移走所花的时间为t[i,j]int[] e = {2,4};//底盘进入装配线i的进入时间为e[i]int[] x = {3,2};//装配完成的汽车离开装配线i的离开时间为x[i]int[][] f = new int[2][n];//f[i][j]表示一个底盘从起点到装配站si,j的最快可能时间int[][] l = new int[2][n];//l[i][j]为装配线的编号，通过装配站si,j的最快路线的上一站在该装配线上int ll=0;//ll为底盘离开装配线时的装配线编号System.out.println("通过装配线的最短时间为："+fasetestway(a,t,e,x,n,f,l,ll));printline(l,ll,n);}public static int fasetestway(int[][] a,int[][] t,int[] e,int[] x,int n,int[][] f,int[][] l,int ll){//int[][] f = new int[2][n];   // int[][] l = new int[2][n];int ff;//初始化f[0][0] = e[0]+a[0][0];f[1][0] = e[1]+a[1][0];for(int j =1;j<n;j++){if(f[0][j-1]+a[0][j] <= f[1][j-1]+t[1][j-1]+a[0][j]){f[0][j] = f[0][j-1]+a[0][j];l[0][j]=0;}else{f[0][j] =f[1][j-1]+t[1][j-1]+a[0][j];    l[0][j]=1;}if(f[1][j-1]+a[1][j]<=f[0][j-1]+t[0][j-1]+a[1][j]){f[1][j]=f[1][j-1]+a[1][j];l[1][j] =1;}else{f[1][j]=f[0][j-1]+t[0][j-1]+a[1][j];l[1][j] =0;}}if(f[0][n-1]+x[0]<=f[1][n-1]+x[1]){ff = f[0][n-1]+x[0];ll=0;}else{ff = f[1][n-1]+x[1];ll = 1;}return ff;}public static void printline(int[][] l,int ll,int n){int i = ll;System.out.println("装配线："+i+",装配站："+(n-1));for(int j =n-1;j>=1;j--){ i = l[i][j]; System.out.println("装配线："+i+",装配站："+(j-1));}}}

输出结果

通过装配线的最短时间为：38
装配线：0,装配站：5
装配线：1,装配站：4
装配线：1,装配站：3
装配线：0,装配站：2
装配线：1,装配站：1
装配线：0,装配站：0