算法导论之装配线调度（动态规划思想）

一.装配线调度问题

$Colonel$公司在有两条装配线的工厂里生产汽车。一个汽车底盘在进入每一条装配线后，在一些装配站中会在底盘安装部件，然后完成的汽车在装配线的末端离开。每条装配线上有n个装配站，编号分别为$j=1,2,......,n$。将装配线$i$($i$为$0$或$1$)的第$j$个装配站表示为$s[i][j]$。装配线$1$的第$j$个站与装配线$2$的第$j$个站执行同样的功能。

然而，这些装配站是在不同时间建造的，而且采用了不同的技术，所以每个站所需时间不同。我们把在装配站s[i][j]所需装配时间记为$a[i][j]$。一个汽车底盘进入其中一条装配线，然后从一站进行到下一站。

初始状态下，底盘进入装配线$i$所需时间为$e[i]$，装配完成后离开装配线$i$所需时间为$x[i]$。

正常情况下，一个底盘进入一条装配线后，它只会经过该条装配线。在相同装配线中，从一个装配站到下一个装配站，所需时间可以忽略。

偶尔来了一个特别急的订单，客户要求尽可能快地制造这些汽车。对这些加急的订单，底盘依然依次经过n个装配站，但是工厂可将部分完成的汽车在任何装配站上从一条装配线移到另一条装配线上。把已经通过装配站$s[i][j]$的一个底盘从装配线$i$移走所需时间为$t[i][j]$，其中$i=0,1$。而$j=1,2,......,n-1$(因为在第$n$个装配站后，装配已完成)。

你需要编一个程序,来确定汽车通过工厂的最短时间为多少。

二.考虑状态设计

设dp[i][j]为到达装配线i，装配站j的最短时间。

初值：

$$dp[0][1]=a[0][1]+a[0][2]$$
$$dp[1][1]=a[1][1]+a[1][2]$$

转移方程

$$dp[0][j]=min(dp[0][j-1],dp[1][j-1]+t[1][j-1])+a[0][j+1]$$

$$dp[1][j]=min(dp[1][j-1],dp[0][j-1]+t[0][j-1])+a[1][j+1]$$
或是
$$dp[i][j]=min(dp[i][j-1],dp[!i][j-1]+t[!i][j-1])+a[0][j+1]$$

答案:

$$min(dp[0][n]+a[0][n+2],dp[1][n]+a[1][n+2])$$

三.程序实现

#include <bits/stdc++.h>
#define MAXN 1000005
#define Copyright (c) 2021.11.7 lAICZ.All rights reserved.
using namespace std;
int n,         //每条生产线上有n个装配站a[2][MAXN],//底盘离开装配站s[i][j]所需时间 t[2][MAXN],//把已经在s[i][j]完成装配的底盘移到s[i + 1 % 2]所需时间 dp[2][MAXN]//汽车第i条线上, 第j个装配站的最短装配时间
;
void readin(){//快读万岁 scanf("%d",&n);for(int i = 0;i <= 1;i++){for(int j = 1;j <= n + 2;j++){scanf("%d",&a[i][j]);}}for(int i = 0;i <= 1;i++){for(int j = 1;j <= n - 1;j++){scanf("%d",&t[i][j]);}}
}
/*
void put(){//测试dp数组是否正确 for(int i = 1;i <= n;i++){cout<<"到达装配站s[0]"<<"["<<i<<"]的最短时间是"<<dp[0][i]<<endl; cout<<"到达装配站s[1]"<<"["<<i<<"]的最短时间是"<<dp[1][i]<<endl; }
}
*/ int main(){readin();dp[0][1] = a[0][1] + a[0][2];dp[1][1] = a[1][1] + a[1][2];for(int j = 2;i <= n;i++){dp[0][i] = min(dp[0][i - 1],dp[1][i - 1] + t[1][i - 1]) + a[0][i + 1];dp[1][i] = min(dp[1][i - 1],dp[0][i - 1] + t[0][i - 1]) + a[1][i + 1];}//put();//输出dp数组 int result = min(dp[0][n] + a[0][n + 2],dp[1][n] + a[1][n + 2]);cout<<result;return 0;
}

四.收获与总结

我们发现,对于求$dp[i][j]$这件事情，我们首先要求出$dp[i][j]$与$dp[!i][j]$

这意味着这个问题具有以下两种非常重要的性质：

1.最优子结构性质（即无后效性原则）
　　所求问题的最优子结构性质是采用动态规划算法的条件之一，这种性质又被称为最优化原理。动态规划方法采用最优化原理来建立用于计算最优解的递归式。所谓最优化原理即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯以构造最优解。当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助我们高效地解决问题。
　　
2.子结构重迭性质
　　人们总希望编写一个简单的递归程序来求解动态规划递归方程。然而，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题，复杂性将大幅度下降。这种方法的思想是：由程序设置“备忘录”，每计算出一个新的子结构的解时，都保存起来。当遇到一次递归时，判断是否已经计算，如果已经计算，只需取出先前保存的结果既可。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。

这两种性质是任意问题能否使用动态规划思想解决的充分必要条件。