动态规划之装配线问题

 

/**

 * 动态规划之装配线问题：

 * 有两条装配线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;
		}
		@Override
		public 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]