建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
原來(lái)打算把算法導(dǎo)論在7月份前搞定，現(xiàn)在已經(jīng)過(guò)去一個(gè)多月了，才只看到第15章，后面也只零散看了一些，不知道假期前能否看完。。。夠嗆啊，馬上要期末考試了，上學(xué)期GPA不到2，被學(xué)位警告了，雖說(shuō)以后不學(xué)這個(gè)專業(yè)了，但起碼成績(jī)單上也不能有掛科是吧。。。要是平時(shí)一點(diǎn)不看，考前靠春哥，曾哥，關(guān)公哥都不行啊。。。這進(jìn)度，郁悶！
盡力吧！
順便還是說(shuō)兩句話：
1.有些書上分析的相當(dāng)好了，我不想做畫蛇添足的人，所以有的地方我會(huì)適當(dāng)省略，當(dāng)然也不是說(shuō)我總結(jié)的地方就是書上講的不好的地方，只是沒(méi)人有一套自己的理解方式，我用自己的話去總結(jié)了，當(dāng)時(shí)也就是最適合我的知識(shí)！所以，建議大家多寫一些算法總結(jié)，你會(huì)體會(huì)到好處的！
2.而且我這個(gè)的性質(zhì)是總結(jié)，不是對(duì)一個(gè)算法的具體講解，所以不先看書，大家應(yīng)該讀不懂的，就比如下面，題目我就沒(méi)有貼出來(lái)，大家不看數(shù)，肯定就讀不懂，我的目的是大家看完書后，謝謝總結(jié)，或者看看別人寫的總結(jié)，說(shuō)不定可以發(fā)現(xiàn)自己哪些地方理解錯(cuò)了，哪些地方不理解，或是哪些地方值得探討。
建議先看看前言：http://www.wutianqi.com/?p=2298
這一次主要是分析15.1節(jié)的例子—裝配線調(diào)度問(wèn)題。
題目有點(diǎn)長(zhǎng)，首先得把題目讀懂。
這個(gè)例子書上花了6面紙的篇幅來(lái)詳細(xì)分析，由此可見(jiàn)其重要性。
談到DP,不得不說(shuō)的就是暴力法，大家都知道，如果用暴力解決類似問(wèn)題，一般時(shí)間復(fù)雜度都是非常非常的高，這個(gè)時(shí)候救世主DP就出來(lái)了，DP以避免了許多重復(fù)的計(jì)算，而大大降低了時(shí)間復(fù)雜度。
按照書上的四個(gè)步驟，我在這里提取一些重點(diǎn)，建議還是把P194~196這四步完整步驟看書上的分析。只有慢慢品味，你才會(huì)發(fā)現(xiàn)《算法導(dǎo)論》的美。
步驟一：
分析問(wèn)題，比如一個(gè)底盤要到達(dá)S[1][j]，則有兩種情況，第一種是從S[1][j-1]到S[1][j]，第二種是從S[2][j-1]到S[1][j]。找出這兩者所花時(shí)間的最小，則就是S[1][j]所需時(shí)間的最小。
這就是有局部最優(yōu)解求全局最優(yōu)解。也就是說(shuō)，一個(gè)問(wèn)題的最優(yōu)解包含了子問(wèn)題的一個(gè)最優(yōu)解。我們稱這個(gè)性質(zhì)為最優(yōu)子結(jié)構(gòu)。這是是否可以應(yīng)用DP的標(biāo)志之一。
步驟二：
找出這個(gè)遞歸關(guān)系，由步驟一可以得到這個(gè)遞歸關(guān)系：
步驟三：
因?yàn)檫f歸的關(guān)系，一般總是可以轉(zhuǎn)換為非遞歸的算法。
由已知量f1[1], f2[1]逐步推出未知量，推啊推，推啊推，最后就推到結(jié)果了~~~~
步驟四：
再由已知結(jié)果返回求路徑。
這一節(jié)最給力的就是這個(gè)例子以及相應(yīng)的圖：
拿起筆，用書上給出的例子，分析這個(gè)圖！
以下是代碼：
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: 《算法導(dǎo)論》15.1 裝配線調(diào)度
*/
#include <iostream>
using namespace std;
int n; // 一個(gè)裝配線上有n個(gè)裝配站
int e1, e2; // 進(jìn)入裝配線1,2需要的時(shí)間
int x1, x2; // 離開裝配線1,2需要的時(shí)間
int t[3][100]; // t[1][j]表示底盤從S[1][j]移動(dòng)到S[2][j+1]所需時(shí)間,同理t[2][j]
int a[3][100]; // a[1][j]表示在裝配站S[1][j]所需時(shí)間
int f1[100], f2[100]; // f1[j], f2[j]分別表示在第一/第二條裝配線上第j個(gè)裝配站的最優(yōu)解
int ln1[100], ln2[100];// ln1[j]記錄第一條裝配線上,最優(yōu)解時(shí)第j個(gè)裝配站的前一個(gè)裝配站是第一條線還是第二條線上
int f, ln; // 最優(yōu)解是,f代表最小花費(fèi)時(shí)間，ln表示最后出來(lái)時(shí)是從裝配線1還是裝配線2
void DP()
{
f1[1] = e1 + a[1][1];
f2[1] = e2 + a[2][1];
for(int j=2; j<=n; ++j)
{
// 處理第一條裝配線的最優(yōu)子結(jié)構(gòu)
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;
}
// 處理第二條裝配線的最優(yōu)子結(jié)構(gòu)
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 << "輸入裝配站的個(gè)數(shù): ";
cin >> n;
cout << "輸入進(jìn)入裝配線1，2所需的時(shí)間e1, e2 :";
cin >> e1 >> e2;
cout << "輸入離開裝配線1, 2所需的時(shí)間x1, x2: ";
cin >> x1 >> x2;
cout << "輸入裝配線1上各站加工所需時(shí)間a[1][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[1][i];
cout << "輸入裝配線2上各站加工所需時(shí)間a[2][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[2][i];
cout << "輸入裝配線1上的站到裝配線2上的站所需時(shí)間t[1][j]: ";
//注意這里是i<n，不是i<=n
for(int i=1; i<n; ++i)
cin >> t[1][i];
cout << "輸入裝配線2上的站到裝配線1上的站所需時(shí)間t[2][j]: ";
for(int i=1; i<n; ++i)
cin >> t[2][i];
DP();
cout << "最快需要時(shí)間: " << f << endl;
cout << "路線是: " << endl;
PrintStation();
cout << endl;
} |
最后還是要感嘆一下，《算法導(dǎo)論》講的真是棒極了，希望大家能靜下心把這一章節(jié)好好看看。
在我獨(dú)立博客上的原文：http://www.wutianqi.com/?p=2496
歡迎大家互相學(xué)習(xí)，互相進(jìn)步！