第4

第4

在前面的内容中，我们介绍过用穷举法设计“装配线与工作站问题”的算法实现，这一课我们将介绍如何用动态规划法设计这个问题的算法实现。两种不同的设计思想它们的算法实现肯定也是相差千里，穷举法中的遍历过程需要算法代码显式控制，而动态规划法的遍历过程则是算法本身隐含的，说具体一点，就是隐含在状态递推的过程中。在开始本课的内容之前，请大家再回忆一下第4-1课的内容，用动态规划思想设计算法实现，需要明确的三个问题：子问题与决策阶段状态的定义、状态递推关系式、边界条件。

问题回顾

为了便于理解本课的内容，在开始算法分析之前，再回顾一下这个题目：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) 执行相同的功能。然而这些工作站是在不同的时间建造的࿰