DP34 流水线调度问题 Assembly Line Scheduling @geeksforgeeks - c++编程基础

overlapping sub-problems. There are two ways to reach station S_{1, j}:

_{1, j-1}

_{2, j-1}

So, to find the minimum time to leave station S_{1, j} the minimum time to leave the previous two stations must be calculated(as explained in above recursion).
Similarly, there are two ways to reach station S_{2, j}:

_{2, j-1}

_{1, j-1}

Please note that the minimum times to leave stations S_{1, j-1} and S_{2, j-1} have already been calculated.

So, we need two tables to store the partial results calculated for each station in an assembly line. The table will be filled in bottom-up fashion.

Note:
In this post, the word “leave” has been used in place of “reach” to avoid the confusion. Since the car chassis must spend a fixed time in each station, the word leave suits better.

流水线调度问题，DP的经典例子。到达某一装配点的货物既可以由本流水线过来，也可以由另一支流水线过来，取决于哪一个更合算。

以下例子答案：

Output:

Figure-2
The bold line shows the path covered by the car chassis for given input values.

package DP;

public class AssemblyLineScheduling {

	public static void main(String[] args) {
		int[][] a = {{4, 5, 3, 2},
                		 {2, 10, 1, 4}};
		int[][] t = {{0, 7, 4, 5},
                		 {0, 9, 2, 8}};
		int[] e = {10, 12};
		int[] x = {18, 7};
		System.out.println(carAssemblyDP(a, t, e, x));
		System.out.println(carAssembly(a, t, e, x));
	}
	
	public static int carAssembly(int[][] a, int[][] t, int[] e, int[] x){
		int n = a[0].length-1;
		return Math.min(carAssemblyRec(a,t, e, x, n, 0) + x[0], 
								carAssemblyRec(a,t, e, x, n, 1) + x[1]);
	}
	
	public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
		if(n == 0){
			return e[line] + a[line][0];
		}
		
		int T0 = Integer.MAX_VALUE;
		int T1 = Integer.MAX_VALUE;
		if(line == 0){		// 以下只适用于line0
			T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],				// 从本线路过来的
								carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);	// 从另一条线路过来的
		}else if(line == 1){		// 以下只适用于line1
			T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],				// 从本线路过来的
								 carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);	// 从另一条线路过来的
		}
		
		return Math.min(T0, T1);
	}

	public static int carAssemblyDP(int[][] a, int[][] t, int[] e, int[] x){
		int n = a[0].length;
		int[] T1 = new int[n];
		int[] T2 = new int[n];
		
		T1[0] = e[0] + a[0][0];
		T2[0] = e[1] + a[1][0];
		
		for(int i=1; i
     
      


      


      

      吐槽一下这题的递归，一开始我是这样写的：

      
      	public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
		if(n == 0){
			return e[line] + a[line][0];
		}
		
		int T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],
								 carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);
		int T1 = Math.min(carAssemblyRec(a, t, e, x, n-1, 1) + a[1][n],
								 carAssemblyRec(a, t, e, x, n-1, 0) + t[0][n] + a[1][n]);
		
		return Math.min(T0, T1);
	}
      

结果和DP的不一样，于是在哪里想了半天哪里出问题，费了好大功夫，用debugger单步跟踪才发现原来是忘记加限制条件了！！！
      

      正确写法应该是：

      
      	public static int carAssemblyRec(int[][] a, int[][] t, int[] e, int[] x, int n, int line){
		if(n == 0){
			return e[line] + a[line][0];
		}
		
		int T0 = Integer.MAX_VALUE;
		int T1 = Integer.MAX_VALUE;
		if(line == 0){		// 以下只适用于line0
			T0 = Math.min(carAssemblyRec(a, t, e, x, n-1, 0) + a[0][n],				// 从本线路过来的
								carAssemblyRec(a, t, e, x, n-1, 1) + t[1][n] + a[0][n]);	// 从另一条线路过来的
		}else if(line == 1){		// 以下只适用于line1
			T1 = Math.m

DP34 流水线调度问题 Assembly Line Scheduling @geeksforgeeks(二)