某个汽车工厂共有两条装配线,每条有 n 个装配站。装配线 i 的第 j个装配站表示为 Si,j ,在该站的装配时间为 ai,j 。一个汽车底盘进入工厂,然后进入装配线 i(i 为 1 或 2),花费时间为 ei 。在通过一条线的第 j 个装配站后,这个底盘来到任一条装配线的第(j+1)个装配站。如果它留在相同的装配线,则没有移动开销。但是,如果它移动到另一条线上,则花费时间为 ti,j 。在离开一条装配线的第 n 个装配站后,完成的汽车底盘花费时间为 xi 离开工厂。待求解的问题是,确定应该在装配线 1 内选择哪些站,在装配线 2 内选择哪些站,才能使汽车通过工厂的总时间最短。
问题提供的变量ei：进入装配线i的时间
aij：在装配站ij所花费的时间
tij：从装配站ij装配完成之后离开该装配线额外花费的时间
xi：装配完成离开i的时间
二、思路分析观察一条通过装配站 S1,j 的最快路线,发现它必定是经过装配线 1 或2 上的装配站(j-1)。因此,通过装配站 S1,j 的最快路线只能是以下二者之一:
• 通过装配站 S1,j−1 的最快路线,然后直接通过装配站 S1,j 。
• 通过装配站 S2,j−1 的最快路线,从装配线 2 转移到装配线 1,然后通过装配站 S1,j 。
故寻找通过任一条装配线上的装配站 j 的最快路线,我们可以规划为先寻找通过两条装配线上的装配站 j-1 的最快路线。
j-1的最优情况可以由j-2的情况来确定，一直向前能推到S0,0和S1,0，而S0,0可以由e0和a0，0相加来确定，S1,1可以由e1和a1，0相加来确定。
三、代码实现代码用path存放路径，表示最短路径代表的装配线，其他数据结构含义见注释。
int main() { //两条装配线 //进入装配线i的时间 int e[2] = {1,2}; //在装配站ij所花费的时间 int a[2][6] = { {4,2,3,5,3},{7,2,4,2,4} }; //从装配站ij装配完成之后离开该装配线额外花费的时间 int t[2][6] = { {2,3,2,2,1},{1,1,2,4,2} }; //装配完成离开i的时间 int x[2] = {2,1}; //用path存放最短路径 int path[6] = { 0 }; //每条装配线包含的装配站个数 int n = 6; //result[i][j]表示离开装配站ij所花费的最少时间 int result[2][6] = {0}; result[0][0] = e[0] + a[0][0]; result[1][0] = e[1] + a[1][0]; if (result[0][0] < result[1][0]) path[0] = 0; else path[0] = 1; for (int j = 1; j < n; j++) { if (result[0][j - 1] < result[1][j - 1] + t[1][j - 1]) result[0][j] = result[0][j - 1] + a[0][j]; else result[0][j] = result[1][j - 1] + a[0][j] + t[1][j - 1]; if (result[0][j - 1] + t[0][j - 1] < result[1][j - 1]) result[1][j] = result[0][j - 1] + a[1][j] + t[0][j-1]; else result[1][j] = result[1][j-1] + a[1][j]; //保存路径 if (result[0][j] < result[1][j]) path[j] = 0; else path[j] = 1; } result[0][5] = result[0][5] + x[0]; result[1][5] = result[1][5] + x[1]; for (int i = 0; i < 5; i++) cout << path[i] << endl; if (result[0][5] < result[1][5]) cout << result[0][5] <<endl; else cout << result[1][5] << endl; system("pause"); return 0; }