动态规划经典算法之装配站调度问题源代码

//Dynamic Programming经典算法之装配站调度问题
//Author:	milo
//Email:	[email protected]
//Date:		2011/11/16 13:47
#include <stdio.h>
#include <stdlib.h>

static int a1[6]={7,9,3,4,8,4};//1号装配线的每个装配站装配时间
static int a2[6]={8,5,6,4,5,7};//2号装配线的每个装配站装配时间

static int e1=2,e2=4;//入装配线消耗
static int x1=3,x2=2;//出装配线消耗

static int t1[5]={2,3,1,3,4};//从装配线1的装配站到装配线2的下一装配站时间消耗
static int t2[5]={2,1,2,2,1};//从装配线2的装配站到装配线1的下一装配站时间消耗

static int f1[6];//到1号装配线的每一个装配站的最小时间消耗
static int f2[6];//到2号装配线的每一个装配站的最小时间消耗
static int f_;//装配完成时间的最小消耗

static int s1[6];//到1号装配线的对应装配站前走的装配线号
static int s2[6];//到2号装配线的对应装配站前走的装配线号
static int s_;//装配完成时走的最后一条装配线号

//装配站调度核心算法之DP代替递归
static void assembly()
{
	/*1. 入装配站时间消耗*/
	f1[0]=e1+a1[0];
	f2[0]=e2+a2[0];//初始化第一个装配站的最小时间消耗

	/*2. 装配线内部最小时间消耗*/
	int i;
	for(i=1;i<6;i++){//顺序求解2-5个装配站的最小时间消耗
		if(f1[i-1]+a1[i] < f2[i-1]+t2[i-1]+a1[i]){//处理1号装配线第i号装配站
			f1[i]=f1[i-1]+a1[i];
			s1[i]=1;
		}else{
			f1[i]=f2[i-1]+t2[i-1]+a1[i];
			s1[i]=2;
		}
		if(f2[i-1]+a2[i] < f1[i-1]+t1[i-1]+a2[i]){//处理2号装配线第i号装配站
			f2[i]=f2[i-1]+a2[i];
			s2[i]=2;
		}else{
			f2[i]=f1[i-1]+t1[i-1]+a2[i];
			s2[i]=1;
		}
	}
	/*3. 出装配线时间消耗*/
	if(f1[5]+x1 < f2[5]+x2){//处理出装配线的情况
		f_=f1[5]+x1;
		s_=1;
	}else{
		f_=f2[5]+x2;
		s_=2;
	}

}

/*用于输出最小消耗装配过程，非递归实现
  降序输出，递归过程升序输出，自己写的
  递归过程感觉很狗屎，有写的精炼的记得
  发我邮箱啊，因为狗屎，本身已是个简单
  过程就不详加注视了*/
static int station=5;
static void print_path()
{
	/*注释部分为非递归实现*/
	//int line=s_;
	//printf("%dth\tline , %dth\tstation\n",s_,5);
	//int i;
	//for(i=5;i>0;i--){
	//	if(line==1){
	//		line=s1[i];
	//	}else{
	//		line=s2[i];
	//	}
	//	printf("%dth\tline , %dth\tstation\n",line,i-1);
	//}
	static int line=s_;
	if(station<0)
		return;
	int line_cp=line;
	if(line==1){
		line=s1[station];
	}else{
		line=s2[station];
	}
	station--;
	print_path();
	line=line_cp;
	station++;
	printf("%dth\tline | %dth\tstation\n",line,station);
}

int main(int argc,char *argv[])
{
	assembly();/*核心算法处理，获取结果*/
	printf("min total timecost:\t%d (s)\n",f_);/*输出最小值*/
	printf("===============================\n");
	print_path();/*输出最小时间消耗装配序列*/
	return 0;
}//Dynamic Programming经典算法之装配站调度问题
//Author:	mil