第3-1课：装配线与工作站问题（穷举）

第一次看到“装配线与工作站问题”是老师在课堂上出的一个题目，当时脑子简单，直接就用穷举法给解了，后来看到《算法导论（第二版）》这本书用的是动态规划算法来解决的，实际测试后发现其效率是穷举法的四、五倍，感觉十分神奇，后来理解了动态规划的原理之后，也就不觉得神奇了。

第 3 部分的内容是介绍穷举法在算法设计中的应用，所以我们先介绍如何用穷举法来解决这个问题，当介绍第 4 部分动态规划内容时，我会再具体介绍如何用动态规划的思想来设计这个算法。

算法分析

首先介绍一下这个题目：Colonel 汽车公司在有两条装配线的工厂内生产汽车，一个汽车底盘在进入每一条装配线后，在每个工作站会在汽车底盘上安装不同的部件，最后完成的汽车从装配线的末端离开，如图（1）所示：

图（1）装配线与工作站问题图示例

每一条装配线上有 n 个工作站，编号为 j=1、2、…、n，把装配线 i（i 为 1 或 2）的第 j 个工作站表示为 S(i，j)。装配线 1 的第 j 个工作站 S(1，j) 和装配线 2 的第 j 个工作站 S(2，j) 执行相同的功能，然而这些工作站是在不同的时间建造的，并且采用了不同的技术，因此，每个工作站上完成装配所需要的时间也不相同，即使是在两条装配线相同位置的工作站也是这样。把每个工作站上所需要的装配时间记为 a