《算法导论》之装配线调度问题

题目：

Paste_Image.png

Paste_Image.png

Paste_Image.png

Paste_Image.png

思路：
其实书中给出了具体的解题的思路，这里我做个总结。
首先，不能给题目吓到了，初学者可能会比较困惑，就是这种题，我没有下手的点，但是对于老手来说，这种题就是一个基本的题，不管怎样，这道题，基本上涵盖了DP解题的基本思路。
具体的解法参考书籍，这里仅仅给出我理解的代码。

代码如下：

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

vector<int> CalMinPath(const vector<int> & a1,
            const vector<int> & a2,
            const vector<int> & e1,
            const vector<int> & e2,
            int n1Start,
            int n2Start,
            int n1End,
            int n2End)
{
    assert(a1.size() > 0);
    assert(a1.size()==a2.size() && e1.size()==e2.size());

    int N = a1.size();

    vector<int> f1(N, 0);
    vector<int> f2(N, 0);
    vector<int> l1(N, 0);
    vector<int> l2(N, 0);
    vector<int> path;

    f1[0] = n1Start;
    f2[0] = n2Start;
    l1[0] = 1;
    l2[0] = 2;

    for (int i=1; i<N; ++i) {
        if (a1[i] + f1[i-1] < a1[i] + f2[i-1] + e2[i-1]) {
            f1[i] = a1[i] + f1[i-1];
            l1[i] = 1;
        } else {
            f1[i] = a1[i] + f2[i-1] + e2[i-1];
            l1[i] = 2;
        }

        if (a2[i] + f2[i-1] < a2[i] + f1[i-1] + e1[i-1]) {
            f2[i] = a2[i] + f2[i-1];
            l2[i] = 2;
        } else {
            f2[i] = f2[i-1] + e1[i-1];
            l2[i] = 1;
        }
    }

    if (f1[N-1] + n1End < f2[N-1] + n2End) {
        path.assign(l1.begin(), l1.end());
    } else {
        path.assign(l2.begin(), l2.end());
    }

    return path;
}

           
int main(int argc, char ** argv)
{
    vector<int> a1 = {7, 9, 3, 4, 8, 4};
    vector<int> a2 = {8, 5, 6, 4, 5, 7};
    vector<int> e1 = {2, 3, 1, 3, 4, 0};
    vector<int> e2 = {2, 1, 2, 2, 1, 0};
    int n1Start = 2;
    int n2Start = 4;
    int n1End = 3;
    int n2End = 2;

    vector<int> nLuxian = CalMinPath(a1, a2, e1, e2, n1Start, n2Start, n1End, n2End);

    for (int i=0; i<nLuxian.size(); ++i) {
        cout << nLuxian[i] << " ";
    }
    cout << endl;

    return 0;
}

这道题的代码，在一开始我是没有想到的，就是采用自底向上的算法，我一直写代码喜欢使用自顶向下的方式。