Algorithm-算法导论装配线问题

发表于 | 分类于 |

最近收到了几份笔试邀请，发现大厂都爱考算法问题，真是让人很无语
不过也没事，你们爱考什么，我就爱搞什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// AssembleLineProblem.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

/**
装配线问题，装配线2条，装配站6个
来源：《算法导论》第四版中文版P192
分类：动态规划，算法，ACM
@Author:XiaJun
@Time:May 3rd,2018
**/

//在装配线上装配的时间
int assembleTime[2][6] = {{7,9,3,4,8,4},{8,5,6,4,5,7}};

//转移的时间
int transTime[2][6] = {{2,2,1,2,2,1},{4,2,3,1,3,4}};

//最后一道流程装配完成后到下线的时间
int offLineTime[2][1] = {{3},{2}};

//求最小值
int getMin(int a,int b) {
	return a < b?a:b;
}

int main()
{
	//存放到达第几个装配站的最短时间，f[1][1]表示到达第2条装配线的第2个装配站的最短时间
	int fast[2][6];
	//初始化，C语言这一点很蛋疼
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 6;j++)
			fast[i][j] = 0;
	//初始化装配站1的最短时间
	fast[0][0] = transTime[0][0]+assembleTime[0][0];
	fast[1][0] = transTime[1][0]+assembleTime[1][0];

	//开始计算
	for(int j = 1;j < 6;j++) {
		//从同一条生产线直接投送过来所需的时间
		int sameLine = fast[0][j-1]+assembleTime[0][j];
		//从另一条生产线转移过来所需的时间
		int otherLine = fast[1][j-1]+assembleTime[0][j]+transTime[0][j];
		fast[0][j] = getMin(sameLine,otherLine);

		//从同一条生产线直接投送过来所需的时间
		sameLine = fast[1][j-1]+assembleTime[1][j];
		//从另一条生产线转移过来所需的时间
		otherLine = fast[0][j-1]+assembleTime[1][j]+transTime[1][j];
		fast[1][j] = getMin(sameLine,otherLine);
	}

	//最终的结果
	int result = getMin(fast[0][5]+offLineTime[0][0],fast[1][5]+offLineTime[1][0]);
    printf("最短的装配时间：%d",result);
	return 0;
}