1.装配线调度
共有两条装配线,每条有N个装配站,装配线i的第j个装配站装配时间为a[i,j],一个汽车进入装配线i,花费时间e[i],如果在装配站[i,j]之后转移到另外一条线则花费t[i,j].在离开一条线的第N个装配站后,完成的汽车花费时间x[i]离开工厂,待求解的问题是在装配线1选择哪些站,在装配线2选择哪些站使通过总时间最小,时间复杂度O(n)。
#define N 6
int f[3][N+1];//f[i,j]表示从起点到站[i,j]的最快时间,
int l[3][N+1];//l[i,j]为装配线编号,其站j-1被通过[i,j]的最快路线使用
static int lbest,fbest;//装配线lbest的站......
阅读全文