算法導論：動態規劃經典案例——裝配線調度問題深度解析

編輯：關於C語言

前言：與《算法導論》的賽跑

原本計劃在七月前攻克《算法導論》，如今已過一個多月，僅推進至第 15 章，後續章節也僅有零星閱讀。期末考試逼近，上學期 GPA 不足 2.0 已遭學位警告，雖不再從事本專業，但成績單上不能有挂科。平時不複習，臨考靠「春哥、曾哥、關公哥」也無濟於事，這進度確實令人焦慮。只能盡力而為了。

關於總結的兩點說明

書中許多分析已相當透徹，我不欲畫蛇添足，故適當省略；並非書中講得不好，而是每人理解路徑不同，我用自己的語言重述，當時最適合我的認知。建議大家多寫算法總結，收穫極大。
本文性質為總結，非具體講解，未先看書恐難讀懂（題目未貼出）。目的是讀完書後參考總結，或看他人總結，發現自己理解偏差、盲區或值得探討之處。

15.1 節案例：裝配線調度問題

書中用 6 頁篇幅詳細分析此例，可見其重要性。談到動態規劃（DP），繞不開暴力法：暴力解決此類問題時間複雜度極高，DP 通過避免重複計算大幅降低複雜度。

四步驟核心提煉（建議閱讀原書 P194~196 完整步驟）

步驟一：識別最優子結構

底盤到達站點 S[1][j] 有兩種路徑：從 S[1][j-1] 直行，或從 S[2][j-1] 轉線。取兩者耗時最小值即為 S[1][j] 的最優解。這正是「局部最優推導全局最優」，即問題的最優解包含子問題的最優解——最優子結構，是適用 DP 的標誌之一。

步驟二：建立遞歸關係

由步驟一可得遞歸公式：

遞歸關係式

步驟三：自底向上計算（消除遞歸）

利用已知量 f1[1], f2[1] 逐步推導未知量，迭代至終點。

步驟四：回溯構造最優路徑

由最終結果反向追蹤，得到完整最優路徑。

關鍵圖解與代碼實現

本節最精華的是配套圖解：

裝配線調度圖解

拿起筆，結合書中數值實例親自推演此圖，方能真悟。

完整 C++ 實現

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
About:  《算法導論》15.1 裝配線調度
*/
#include <iostream>
using namespace std;

int n;                  // 每條裝配線的站數
int e1, e2;             // 進入線 1、2 耗時
int x1, x2;             // 離開線 1、2 耗時
int t[3][100];          // t[1][j]: 從 S[1][j] 轉到 S[2][j+1] 耗時
int a[3][100];          // a[1][j]: 站點 S[1][j] 加工耗時
int f1[100], f2[100];   // f1[j], f2[j]: 線 1/2 第 j 站最優耗時
int ln1[100], ln2[100]; // ln1[j]: 線 1 第 j 站最優路徑來自線 1 或 2
int f, ln;              // 全局最優耗時 f，最後輸出線 ln

void DP() {
    f1[1] = e1 + a[1][1];
    f2[1] = e2 + a[2][1];
    for (int j = 2; j <= n; ++j) {
        // 線 1 第 j 站最優子結構
        if (f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j]) {
            f1[j] = f1[j-1] + a[1][j];
            ln1[j] = 1;
        } else {
            f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
            ln1[j] = 2;
        }
        // 線 2 第 j 站最優子結構
        if (f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j]) {
            f2[j] = f2[j-1] + a[2][j];
            ln2[j] = 2;
        } else {
            f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
            ln2[j] = 1;
        }
    }
    // 最終選擇
    if (f1[n] + x1 <= f2[n] + x2) {
        f = f1[n] + x1;
        ln = 1;
    } else {
        f = f2[n] + x2;
        ln = 2;
    }
}

void PrintStation() {
    int i = ln;
    cout << "line " << i << ", station " << n << endl;
    for (int j = n; j >= 2; --j) {
        if (i == 1) i = ln1[j];
        else        i = ln2[j];
        cout << "line " << i << ", station " << j-1 << endl;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    cout << "輸入裝配站個數: ";       cin >> n;
    cout << "輸入進入時間 e1, e2: ";   cin >> e1 >> e2;
    cout << "輸入離開時間 x1, x2: ";   cin >> x1 >> x2;
    cout << "輸入線 1 各站加工時間: ";
    for (int i = 1; i <= n; ++i) cin >> a[1][i];
    cout << "輸入線 2 各站加工時間: ";
    for (int i = 1; i <= n; ++i) cin >> a[2][i];
    cout << "輸入線 1→線 2 轉線時間: ";
    for (int i = 1; i < n; ++i)  cin >> t[1][i]; // 注意 i<n
    cout << "輸入線 2→線 1 轉線時間: ";
    for (int i = 1; i < n; ++i)  cin >> t[2][i];
    DP();
    cout << "最快耗時: " << f << endl;
    cout << "最優路徑: " << endl;
    PrintStation();
    cout << endl;
    return 0;
}