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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
About: 《算法導論》15.1 裝配線調度
*/
#include <iostream>
using namespace std;
int n; // 一個裝配線上有n個裝配站
int e1, e2; // 進入裝配線1,2需要的時間
int x1, x2; // 離開裝配線1,2需要的時間
int t[3][100]; // t[1][j]表示底盤從S[1][j]移動到S[2][j+1]所需時間,同理t[2][j]
int a[3][100]; // a[1][j]表示在裝配站S[1][j]所需時間
int f1[100], f2[100]; // f1[j], f2[j]分別表示在第一/第二條裝配線上第j個裝配站的最優解
int ln1[100], ln2[100];// ln1[j]記錄第一條裝配線上,最優解時第j個裝配站的前一個裝配站是第一條線還是第二條線上
int f, ln; // 最優解是,f代表最小花費時間，ln表示最后出來時是從裝配線1還是裝配線2
void DP()
{
f1[1] = e1 + a[1][1];
f2[1] = e2 + a[2][1];
for(int j=2; j<=n; ++j)
{
// 處理第一條裝配線的最優子結構
if(f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j])
{
f1[j] = f1[j-1] + a[1][j];
ln1[j] = 1;
}
else
{
f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
ln1[j] = 2;
}
// 處理第二條裝配線的最優子結構
if(f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j])
{
f2[j] = f2[j-1] + a[2][j];
ln2[j] = 2;
}
else
{
f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
ln2[j] = 1;
}
}
if(f1[n] + x1 <= f2[n] + x2)
{
f = f1[n] + x1;
ln = 1;
}
else
{
f = f2[n] + x2;
ln = 2;
}
}
void PrintStation()
{
int i= ln;
cout << "line " << i << ", station " << n << endl;
for(int j=n; j>=2; --j)
{
if(i == 1)
i = ln1[j];
else
i = ln2[j];
cout << "line " << i << ", station " << j-1 << endl;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
cout << "輸入裝配站的個數: ";
cin >> n;
cout << "輸入進入裝配線1，2所需的時間e1, e2 :";
cin >> e1 >> e2;
cout << "輸入離開裝配線1, 2所需的時間x1, x2: ";
cin >> x1 >> x2;
cout << "輸入裝配線1上各站加工所需時間a[1][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[1][i];
cout << "輸入裝配線2上各站加工所需時間a[2][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[2][i];
cout << "輸入裝配線1上的站到裝配線2上的站所需時間t[1][j]: ";
//注意這里是i<n，不是i<=n
for(int i=1; i<n; ++i)
cin >> t[1][i];
cout << "輸入裝配線2上的站到裝配線1上的站所需時間t[2][j]: ";
for(int i=1; i<n; ++i)
cin >> t[2][i];
DP();
cout << "最快需要時間: " << f << endl;
cout << "路線是: " << endl;
PrintStation();
cout << endl;
} |