动态规划之装配线问题
?
/**
?* 动态规划之装配线问题：
?* 有两条装配线L1和L2,每条装配线上有n个站，将装配线i(=1或2)的第j个站表示为S[i][j].装配线1和2的第j个站功能相同，但是加工的时间不同，设S[i][j]站得时间为a[i][j]
?* 一个产品进入生产线i的时间为e[i]，完成后离开生产线i的时间为x[i]
?* 一个产品在同一条装配线上从上一站完成后转移到下一站的时间为0，但是从一条装配线L[i]上得一个站S[i][j]转移到另一条装配线上得站S[i'][j+1]需要时间为t[i][j]
?*?
?* 思路：通过S[i][j]站最快的路线，必定是通过S[1][j-1]站最快或者通过S[2][j-1]站最快的路线之一。
?* 设f[i][j]表示从入口到站S[i][j]的最快时间，则我们要求的最小时间
?* f = min(f[1][n]+x[1],f[2][n]+x[2])
?* f[1][1] = e1 + a[1][1], ?f[2][1] = e2 + a[2][1],进一步有：
?* ? ? ? f[1][j] = e1+a[1][1] ?if j == 1
?* ? ? ? ? ? ? ? ? min(f[1][j-1]+a[1][j], f[2][j-1]+t[2][j-1]+a[1][j]) if j >= 2
?* ? ? ? ? ? ? ? ??
?* ? ? ? f[2][j] = e2 + a[2][1] ?if j==1
?* ? ? ? ? ? ? ? ? min(f[2][j-1]+a[2][j], f[1][j-1]+t[1][j-1]+a[2][j]) if j >= 2
?* ? ? ? ? ? ? ? ??
?* ?在计算过程中，我们需要填满一张 2 * n 的表格为f[1][1....n]和f[2][1....n]的值
?* ?此外，我们再定义l[i][j]来记录经过站S[i][j]的上一站S[i][j]的i值1 或者 2，通过这个表的值最终能得到最优装配路线
?* @author song
?*
?*/
?
?
/**
*?
* @param a 通过每一站的时间，a[i][j]为通过i+1（因为数组下标从0开始记，所以i = 0,1）条路线的j+1站得时间，第一维度2， 第二维度 n，j=0,1,...n-1
* @param t 从一条线路转到另一条路线的时间，t[i][j]为从第i+1条路线的第j+1站转移到另一条路线的j+2站所需的时间，第一维2（i = 0,1）， 第二维n - 1（j=0,1,...n-2）
* @param e 长度为2的数组，e[0]表示进入到站S[1][1]的的时间，e[1]表示进入到第二条路线第一站的时间
* @param x 长度为2的数组，x[0]表示离开第一条路线最后一站的时间，x[1]表示离开第二条路线最后站的时间
* @param n 装配线的长度
*/
public static AssembleResult fastestWay(int[][] a, int[][] t, int[] e, int[] x, int n){//用来存经过每一站的最优时间int[][] f = new int[2][n];//用来记录走过的路线int[][] l = new int[2][n-1];//初始化f[0][0] = e[0] + a[0][0]; //经过第1条装配线第一站的时间f[1][0] = e[1] + a[1][0]; //经过第2条装配线第一站的时间for( int i = 1; i < n; ++i){//循环计算f[0][i]和f[1][i]if( f[0][i-1]+a[0][i] < f[1][i-1] + t[1][i-1] + a[0][i]){f[0][i] = f[0][i-1]+a[0][i];l[0][i-1] = 1;}else{f[0][i] = f[1][i-1] + t[1][i-1] + a[0][i];l[0][i-1] = 2;}if(f[1][i-1] + a[1][i] < f[0][i-1] + t[0][i-1] + a[1][i]){f[1][i] = f[1][i-1] + a[1][i];l[1][i-1] = 2;}else{f[1][i] = f[0][i-1] + t[0][i-1] + a[1][i];l[1][i-1] = 1;}}int resultV = 1;int theLastLineOfPath = 1;if( f[0][n-1] + x[0] < f[1][n-1] + x[1]){resultV = f[0][n-1] + x[0];}else{resultV = f[1][n-1] + x[1];theLastLineOfPath = 2;}return new AssembleResult(l,theLastLineOfPath, resultV);}static class AssembleResult{int lastLineOfPath;int[][] path;int value;public AssembleResult(int[][] path,int lastLineOfPath, int value) {this.path = path;this.lastLineOfPath = lastLineOfPath;this.value = value;}@Overridepublic String toString() {return "AssembleResult path=[" + getThePath() + ", value="+ value + "]";}public String getThePath(){StringBuilder sb = new StringBuilder();int lineNum = lastLineOfPath;int stationNum = path[0].length + 1;sb.append("(line").append(lineNum).append(" station").append(stationNum).append(")");for( int i = path[0].length; i > 0 ; --i){lineNum = path[lineNum-1][i-1];stationNum = i;sb.insert(0, "(line"+lineNum+" station"+stationNum+") -->");}return sb.toString();}}?
测试：
?
public static void main(String[] args){int[][] a = new int[][]{{7,9,3,4,8,4},{8,5,6,4,5,7}};int[][] t = new int[][]{{2,3,1,3,4},{2,1,2,2,1}};int[] x = new int[]{3,2};int[] e = new int[]{2,4};int n = 6;AssembleResult r = fastestWay(a, t, e, x, n);System.out.println(r.toString());}?
结果：
?
AssembleResult path=[(line1 station1) -->(line2 station2) -->(line1 station3) -->(line2 station4) -->(line2 station5) -->(line1 station6), value=38]