本文主要是介绍动态规划之装配线调度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考资料：《算法导论第二版第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
这篇关于动态规划之装配线调度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
