动态规划学习记录 二、装配线调配问题

一、装配线调度问题

详细的证明和分析在《算法导论》的第193页

数据结构：s[0][i],s[1][i]

          t[0][i],t[1][i]

算法：自底而上，递推法.

状态转移方程：（哈哈，我自己写的）:

S[1][i]=min(s[0][i-1]+v[1][i]+t[0][i-1, s[1][i-1]+v[1][i]);

边界条件：i==n；

赋初值：s[1][1]=start[1]+v[1][1];

        S[0][1]=start[0]+v[0][1];

最终值：max{s[0][n]+end[0],s[1][n]+end[1]};

//注意：整个过程是单向的，过程是一步步的，不可逆的..

状态：状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性。所谓无后向性即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。

 

#include<iostrea>
#include<string.h>
#define maxn 1000+5
using namespace std;
int d[2][maxn];
int t[2][maxn];
int v[2][maxn];

int st0,st1,ft0,ft1;//分别表示进和出0，1车间的固定时间
int main(){
	cin>>st0>>st1>>ft0>>ft1;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>v[0][i];
	for(int i=1;i<=n;i++)
	cin>>v[1][i];
	for(int i=1;i<=n-1;i++)
	cin>>t[0][i];
	for(int i=0;i<=n-1;i++)
	cin>>t[1][i];
	d[0][1]=v[0][1]+st0;
	d[1][1]=v[1][1]+st1;
	for (int i=2;i<=n;i++){
		d[0][i]=min(d[0][i-1]+v[0][i],d[1][i-1]+v[0][i]+t[1][i-1]);
		d[1][i]=min(d[1][i-1]+v[1][i],d[0][i-1]+v[1][i]+t[0][i-1]);
	}
	cout<<min(d[0][n]+ft0,d[1][n]+ft1);
}