动态规划之车间装配问题

《算法导论》给出了详细的描述，这里归纳下。

算法原理：任意一条装配线中的装配站j的最快路径，都是来自于任意一条装配线中的装配站j-1。

采用算法导论中，给出的图以及数据，如下:

由于采用C语言数组，装配线下标是0或者1，装配站下表是0，1，2，3，4，5，上面的l1和l2数组分别翻译成0 1 0 0 1和0 1 0 1 1。

代码实现如下

fastest_way函数并不保存f1,f2数组，这两个数组仅是辅助作用。其次，为了节约空间，t数组中，包含了离开装配站S(0,5)后，所花费的时间t[0][5]。另一条装配线同理，并且l*数据保存在t[0][0]和t[1][0]中。

template <int n>
int fastest_way(int S[][n], int t[][n], int e1, int e2, int *l1, int *l2) {
    int *f1 = new int[n], *f2 = new int[n], fast = 0;
    f1[0] = e1 + S[0][0];//进入装配线0
    f2[0] = e2 + S[1][0];
    for (int j = 1; j < n; j++) {
        if (f1[j - 1] + S[0][j] <= f2[j - 1] + t[1][j - 1] + S[0][j]) {//来自装配线0的j-1
            f1[j] = f1[j - 1] + S[0][j];
            l1[j] = 0;
        }
        else {//来自装配线1的j-1
            f1[j] = f2[j - 1] + t[1][j - 1] + S[0][j];
            l1[j] = 1;
        }
        if (f2[j - 1] + S[1][j] <= f1[j - 1] + t[0][j - 1] + S[1][j]) {//同理针对装配线1
            f2[j] = f2[j - 1] + S[1][j];
            l2[j] = 1;
        }
        else {
            f2[j] = f1[j - 1] + t[0][j - 1] + S[1][j];
            l2[j] = 0;
        }
    }
    if (f1[n - 1] + t[0][n - 1] <= f2[n - 1] + t[1][n - 1]) {
        fast = f1[n - 1] + t[0][n - 1];
        l1[0] = l2[0] = 0;
    }
    else {
        fast = f2[n - 1] + t[1][n - 1];
        l1[0] = l2[0] = 1;
    }
    delete[] f1;
    delete[] f2;
    return fast;
}

递归显示正确路线

void show_fast(int l, int n, int *l1, int *l2) {//l初始化时l1[0]或l2[0]
    if (n == 0)
        return;
    show_fast(l == 0 ? l1[n-1] : l2[n-1], n - 1, l1, l2);
    printf("Line %d, Assembling at Station %d
", l, n - 1);
}

测试数据：

#define LINE 2 //装配线0,1
#define STATION 6  //装配站0-5

int S[LINE][STATION] = { {7,9,3,4,8,4},{8,5,6,4,5,7} },
        t[LINE][STATION] = { {2,3,1,3,4,3},{2,1,2,2,1,2} },//包含离开最后一个装配站的时间
        e1 = 2, e2 = 4, l1[STATION], l2[STATION];

测试结果（正确，正如前面所述，下标满足C语言数组下标性质，最快装配路线吻合）：

所有代码均经过测试，结果正确！