《算法导论》第十五章第一道习题代码

    经过昨天的笔试，发现自己算法还是蛮弱的，以后有空还是要多看看算法。下面是《算法导论》第十五章第一道习题代码:

package introductionToAlgorithms;

//动态规划求装配线调度最短路线
public class Scheduling {
	static int[] f1 = new int[6];
	static int[] f2 = new int[6];
	static int[] l1 = new int[6];
	static int[] l2 = new int[6];
	static int[][] a = {{7,9,3,4,8,4},{8,5,6,4,5,7}};
	static int last;//l*
	static int e1 = 2, e2 = 4,x1 = 3, x2 = 2;
	static int[][] t = {{2,3,1,3,4},{2,1,2,2,1}};
	static int n = 6;
	static int result;
	static int[] sequence = new int[6];
	
	static void fastestWay() {
		f1[0] = e1 + a[0][0];
		f2[0] = e2 + a[1][0];
		
		for(int j=1; j<n; j++) {
			//更新1号装配线上的f1[i]和l1[i]
			if(f1[j-1] + a[0][j-1] < f2[j-1] + t[1][j-1] + a[0][j] ||
					f1[j-1] + a[0][j-1] == f2[j-1] + t[1][j-1] + a[0][j]) {
				//若从1号装配线花费时间更少
				f1[j] = f1[j-1] + a[0][j];
				l1[j] = 1;
			}
			else {
				f1[j] = f2[j-1] + t[1][j-1] + a[0][j];
				l1[j] = 2;				
			}

			//更新2号装配线上的f2[i]和l2[i]
			if(f2[j-1] + a[1][j-1] < f1[j-1] + t[0][j-1] + a[1][j] ||
					f2[j-1] + a[1][j-1] == f1[j-1] + t[0][j-1] + a[1][j]) {
				//若从2号装配线花费时间更少
				f2[j] = f2[j-1] + a[1][j];
				l2[j] = 2;				
			}
			else {
				f2[j] = f1[j-1] + t[0][j-1] + a[1][j];
				l2[j] = 1;					
			}
		}
		
		if( f1[n-1] + x1 < f2[n-1] + x2 ||
				f1[n-1] + x1 == f2[n-1] + x2) {
			result = f1[n-1] + x1;
			last = 1;
		} else {
			result = f2[n-1] + x2;
			last = 2;
		}
	}
	
	static void printStations() { //逆序打印通过工厂的最快路线
		int i = last;
		System.out.println("line " + i + ", station " + n);
		for(int j = n-1; j>0; j--) {
			if(i == 0)
				i = l1[j];
			else i = l2[j];
			
			System.out.println("line " + i + ", station " + j);
		}
	}
	
	static int findSequence(int k) {
		if(k == n-2) {
			if(last == 1) 
				sequence[k] = l1[n-1];
			else 
				sequence[k] = l2[n-1];		
		}
		else {
			if(findSequence(k+1) == 1) 
				sequence[k] = l1[k+1];
			else
				sequence[k]= l2[k+1];
		}
		
		return sequence[k];
	}
	
	static void printStations2() { //顺序打印通过工厂的最快路线
		int i = last;
		sequence[n-1] = last;
		int k = 0;
		findSequence(k);
		for(int j=0; j<n; j++)
			System.out.println("line " + sequence[j] + ", station" + (j+1));

	}

	public static void main(String[] args) {
		fastestWay(); //先求出最快路线
		printStations2();

	}
}