建議先看看前言：http://www.wutianqi.com/?p=2298
連載總目錄：http://www.wutianqi.com/?p=2403
說到貪心算法，避免不了于DP對比，所以前面的DP要了解。
貪心算法是使所做的選擇看起來都是當前最佳的，期望通過所做的局部最優選擇來產生一個全局最優解。
依然和上一章總結DP一樣，我先給出一個最容易入門的例子，來看看神馬是貪心？(是人就會貪心，這個算法很人性化啊
=。=)
一個最簡單的例子：
部分背包問題：
有N個物品，第i個物品價值vi，重wi，現在你有一個可以裝W 磅的包，你可以選擇帶走每個物品的全部或一部分，求如何選擇可以使背包所裝的價值最大？(這個是不是和前面DP中講的01背包很像？認真看清楚兩者題目的不同！)
假如有三種物品，背包可裝50磅的物品，物品1重10磅，價值60元；物品2重20磅，價值100元；物品3重30磅，價值120元。因此，既然可以選擇只裝一部分，我們可以算出每種物品的單位價值，物品1是每磅6元，物品2是美邦5元，物品3是每磅4元。按照貪心策略，應該現狀物品1，如果裝完物品1背包還有空間，再裝物品2……
最后的結果是：
而如果按01背包，則結果是：
有興趣的可以拿我那01背包的程序去驗證這個結果。
下面是一個部分背包的小程序：
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
|
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct Thing{
double v; // value
double w; // weight
}Thing;
Thing arr[100];
int n;
double W;
bool cmp(Thing a, Thing b)
{
return a.v/a.w > b.v/b.w;
}
int main()
{
cout << "輸入物品個數: ";
cin >> n;
cout << "輸入背包可載重量: ";
cin >> W;
cout << "輸入" << n << "個物品的價值和重量:" << endl;
for(int i=0; i<n; ++i)
cin >> arr[i].v >> arr[i].w;
sort(arr, arr+n, cmp);
int k = 0;
double value = 0;
while(W)
{
if(W >= arr[k].w)
{
W -= arr[k].w;
value += arr[k].v;
}
else
{
value += W * arr[k].v / arr[k].w;
W = 0;
}
++k;
}
cout << "最大價值是: " << value << endl;
return 0;
} |
結果如圖：
posted @
2011-06-14 13:17 Tanky Woo 閱讀(1804) |
評論 (5) |
編輯 收藏看了下上一篇的日期，是5.16號，已經有20天沒寫了，郁悶啊，不過最近的考試終于結束了，接下來就是18號的六級和后面的三門考試，這幾天可以安心研究算法了，開心啊。
建議先看看前言：http://www.wutianqi.com/?p=2298
連載總目錄：http://www.wutianqi.com/?p=2403
這一章，我準備把HDOJ上找幾道經典的DP題目給大家分析一下。
1.HDOJ 1257 最少攔截系統
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1257
分析+代碼：http://www.wutianqi.com/?p=1841
經典的LIS，DP入門級題目。
2.HDOJ 1176 免費餡餅
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1176
分析+代碼：http://www.wutianqi.com/?p=2457
這一題的經典在于由直線向數塔的轉化，圖形分析在上面的連接中給出。
3.HDOJ 1160 FatMouse’s Speed
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1160
分析+代碼：http://www.wutianqi.com/?p=2290
最長上升子序列的問題，題目比較新穎，這里可以感受到我在前面寫的，DP和BFS,遞歸和DFS的關系。
4.HDOJ 1080 Human Gene Functions
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1080
分析+代碼：http://www.wutianqi.com/?p=2413
這題不知道該怎么說，反正個人做了后第一感覺就是經典！特此推薦。
另外，DP的題目個人覺得做多了就有感覺了，以前轉載過牛人總結的HDOJ上46道DP題目，嘿嘿，給出鏈接：
http://www.wutianqi.com/?p=550
誰要全部做完了記得告訴我一聲，我要膜拜一下。
好了，DP到此結束，接下來的將是貪心算法了~~~
Tanky Woo 標簽:
DP，
動態規劃，
Tanky Wooposted @
2011-06-12 09:32 Tanky Woo 閱讀(1880) |
評論 (3) |
編輯 收藏首先說一下，ACM的入門方法多種多樣，大部分人還是跟著學校一起參加集訓，所以我這里主要是想對那些準備ACM入門的業余的朋友談的。
入門書籍：
首先推薦一些ACM的書籍：
(以下我都會給出在當當網的頁面，方便大家直接購買，以下排名不分先后)
1.《程序設計導引及在線實踐》
http://product.dangdang.com/product.aspx?product_id=20051430&ref=search-1-pub
這是我的第一本入門書，這本書是配套北大的百煉習題，注意不是POJ，貌似是北大內部測試用的，不過也是對外開放的，去年好像百煉變化過，所以[u]不知道這本書還適不適合那個新的百煉系統[/u]。
2.《算法競賽入門經典》
http://product.dangdang.com/product.aspx?product_id=20724029&ref=search-1-pub
這本書沒話說，劉汝佳的白書，經典的算法入門書籍。[b]強烈推薦[/b]！
3.《算法藝術與信息學競賽》
http://product.dangdang.com/product.aspx?product_id=8811386&ref=search-1-pub
劉汝佳的黑書，難度較深，題目基本來至Uva，我是看了前面以部分，后面就沒咋看了。。。
4.《算法導論》
http://product.dangdang.com/product.aspx?product_id=9211884&ref=search-1-pub
經典的書籍是不需要解釋的。
這是我曾經上傳過的英文版CHM算法導論，可以下載了看看：
http://www.cppleyuan.com/viewthread.php?tid=5130&highlight=%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA
我最近也在寫算法導論的讀書總結，歡迎大家探討：
http://www.wutianqi.com/?p=2403
5.《編程之美》
http://product.dangdang.com/product.aspx?product_id=20170952&ref=search-1-pub
挺有意思的，不能作為一個算法的全面書籍，而是作為一本拓寬思維的書籍，有興趣的建議要看看。
6.《計算機程序設計藝術》
http://product.dangdang.com/product.aspx?product_id=690222&ref=search-1-pub
有好幾卷的，只給出一卷的連接，而且網上版本很多，大家可以自行選擇。
這個還沒看，關鍵是沒時間了，準備考研完了就趁著假期看完。
7.《組合數學》
http://product.dangdang.com/product.aspx?product_id=8976756&ref=search-0-mix
鴿巢原理，博弈，容斥原理，Catalan數等都屬于這個范疇的，建議看看。
8.《數據結構（C語言版）》嚴蔚敏
http://product.dangdang.com/product.aspx?product_id=9268172&ref=search-1-pub
數據結構，這個必須得學好啊~~~
9.《數據結構與算法分析C++描述（第三版）》
http://product.dangdang.com/product.aspx?product_id=9239535&ref=search-1-pub
有時間可以看看，C++ Template寫的，可以順便鞏固下template。
以下基本都沒看過，不過貌似很有名，給出書名和連接：
10.《世界大學生程序設計競賽（ACM/ICPC）高級教程.第一冊.程序設計中常用的計算思維方式》
http://product.dangdang.com/product.aspx?product_id=20645866&ref=search-1-pub
這本我其實買了，但是還沒有時間看。
11.《國際大學生程序設計競賽指南—ACM程序設計》
http://product.dangdang.com/product.aspx?product_id=20450827&ref=search-1-pub
12.《國際大學生程序設計競賽例題解（三）圖論、動態規劃算法、綜合題專集》
http://product.dangdang.com/product.aspx?product_id=9352432&ref=search-1-pub
這個好像也有好幾冊，每一冊都是單獨講一個方面的。
13.《挑戰編程：程序設計競賽訓練手冊》
http://product.dangdang.com/product.aspx?product_id=20637355&ref=search-1-pub
(作者：Tanky Woo, 個人博客：http://www.wutianqi.com ，C++/算法論壇：http://www.cppleyuan.com/ 。轉載請注明個人及原文連接，謝謝合作)
入門方法：
這么多書，不可能全部都看的，我覺得前10本，也就是我看過的，都還不錯，大家可以看看。
另外，我個人推薦ACM可以這樣入門(以下用到了上面書籍前面的序號)：（當然，如果學校有專門培訓的，則跟著學校來更好）
1.數據結構是基礎，建議先把8號嚴蔚敏老師的《數據結構》好好看1~2遍，代碼都手動敲一敲。
2.再看2號劉汝佳的白書。
3.去年暑假(2010.7~2010.9月)，我曾經給我的論壇(C++奮斗樂園：http://www.cppleyuan.com/)搞過一次ACM專題訓練，訓練題全部來至HDOJ，當時我是由易到難，每天選擇一個專題，在HDOJ上找3~4題，然后在論壇給出題目，大家可以到HDOJ去提交，然后貼到論壇供其他朋友參考。板塊是：http://www.cppleyuan.com/forumdisplay.php?fid=40，前面都是看書，這里就建議大家開始實戰了，在論壇里一共除了200多題，大家一定要做！
4.有了一定的基礎，就可以再一邊進行深入(看書)，一邊做題了。這個時候神馬《算法導論》，《計算機程序設計藝術》等等都可以看看。
5.到了這個階段，沒啥說的了，自由學習~~~
最后說一句：算法魅力，無與倫比，歡迎大家來到ACM的世界！加油！
(作者：Tanky Woo, 個人博客：http://www.wutianqi.com ，C++/算法論壇：http://www.cppleyuan.com/ 。轉載請注明個人及原文連接，謝謝合作)
posted @
2011-06-08 20:08 Tanky Woo 閱讀(4135) |
評論 (2) |
編輯 收藏建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
這個案例也比較簡單，最長公共子序列(LCS)，網上的分析非常多，給力啊！
按照上一篇總結所說的，找狀態轉移方程：
所以按照所給方程，寫代碼的工作就非常非常簡單輕松了：
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
|
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
About: 《算法導論》15.4 最長公共自序列(LCS)
*/
#include <iostream>
using namespace std;
char b[20][20];
int c[20][20];
char x[20], y[20];
void LCS()
{
int m = strlen(x+1);
int n = strlen(y+1);
for(int i=1; i<=m; ++i)
c[i][0] = 0;
for(int j=1; j<=n; ++j)
c[0][j] = 0;
for(int i=1; i<=m; ++i)
for(int j=1; j<=n; ++j)
{
if(x[i] == y[j])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = '\\'; // 注意這里第一個\\是轉移字符，代表\
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = '|';
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = '-';
}
}
}
void printLCS(int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == '\\')
{
printLCS(i-1, j-1);
cout << x[i] << " ";
}
else if(b[i][j] == '|')
printLCS(i-1, j);
else
printLCS(i, j-1);
}
int main()
{
cout << "Input the array A:\n";
cin >> x+1;
cout << "Input the array B:\n";
cin >> y+1;
LCS();
printLCS(strlen(x+1), strlen(y+1));
} |
看書上圖15-6的結果圖：
又是一個給力的圖,建議自己按照程序把這個圖畫出來.
另外,說到LCS,不得不說的是LIS(最長上升子序列)，也是一個DP，我曾經總結過：
http://www.wutianqi.com/?p=1850
Tanky Woo 標簽:
DP，
動態規劃，
LCS
posted @
2011-05-26 18:55 Tanky Woo 閱讀(1529) |
評論 (2) |
編輯 收藏建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
這一節可以看到《算法導論》學習總結 — 16.第15章 動態規劃(1) 基本入門的補充。
采用動態規劃的最優化問題的兩個要素：最優子結構和重疊子問題。
先看看最優子結構：
在第17篇總結時，裝配線調度問題中，已經設計到了最優子結構，證明最優子結構問題可以用書上說的“剪貼技術”，即假設存在更優的解，來反正最優解矛盾。
再看看重疊子問題：
當一個遞歸算法不斷的調用同一個問題時，我們說該最有問題包含“重疊子問題”。
上面這句話不好理解？
看看下面這個比較：
遞歸算法：自頂而下，對在遞歸樹中重復出現的每個子問題都要重復解一次。
動態規劃：自下而上，對每個只解一次。
結合第16篇總結的三角形求值例子，可以看得到，自下而上導致每個子問題只求解一次。
以上理論性有點強，我最開始學DP看的是HDOJ的課件，有興趣的可以去看看。
在那里面，主要講到了是找狀態轉移方程，在第16篇的三角形求值例子和第17篇的裝配線調度例子，那些遞歸公式都是狀態轉移方程。
下面這段話好好理解：
——————————————————————–
動態規劃的幾個概念:
階段：據空間順序或時間順序對問題的求解劃分階段。
狀態：描述事物的性質，不同事物有不同的性質，因而用不同的狀態來刻畫。對問題的求解狀態的描述是分階段的。
決策：根據題意要求，對每個階段所做出的某種選擇性操作。
狀態轉移方程：用數學公式描述與階段相關的狀態間的演變規律。
動態規劃是運籌學的一個重要分支，是解決多階段決策過程最優化的一種方法。
所謂多階段決策過程，是將所研究的過程劃分為若干個相互聯系的階段，在求解時，對每一個階段都要做出決策，前一個決策確定以后，常常會影響下一個階段的決策。
動態規劃所依據的是“最優性原理”。
“最優性原理”可陳述為：不論初始狀態和第一步決策是什么，余下的決策相對于前一次決策所產生的新狀態，構成一個最優決策序列。
最優決策序列的子序列，一定是局部最優決策子序列。
包含有非局部最優的決策子序列，一定不是最優決策序列。
動態規劃的指導思想是：
在做每一步決策時，列出各種可能的局部解，之后依據某種判定條件，舍棄那些肯定不能得到最優解的局部解。這樣，在每一步都經過篩選，以每一步都是最優的來保證全局是最優的。篩選相當于最大限度地有效剪枝（從搜索角度看），效率會十分高。但它又不同于貪心法。貪心法只能做到局部最優，不能保證全局最優，因為有些問題不符合最優性原理。
——————————————————————–
看見有人說遞歸就是DFS，而DP就是BFS，感覺有那么一點意思，對于DP，就是從底層一層層的計算，然后在當層中選取最優，逐層最優以至總體最優。
其實這個還是多做一些題就好了(⊙ｏ⊙)，大家別認為我是做題控，其實說實在話，看N遍不如做一題，說白了，算法數學本一家，算法就是數學，走過高中的，都知道數學題得多做，尤其壓軸題，看N遍不如做一遍，這個也是一樣做幾題就知道DP是神馬東東了！
在我獨立博客上的原文：http://www.wutianqi.com/?p=2500
歡迎大家互相學習，互相進步！
posted @
2011-05-23 12:03 Tanky Woo 閱讀(1592) |
評論 (0) |
編輯 收藏建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
原來打算把算法導論在7月份前搞定，現在已經過去一個多月了，才只看到第15章，后面也只零散看了一些，不知道假期前能否看完。。。夠嗆啊，馬上要期末考試了，上學期GPA不到2，被學位警告了，雖說以后不學這個專業了，但起碼成績單上也不能有掛科是吧。。。要是平時一點不看，考前靠春哥，曾哥，關公哥都不行啊。。。這進度，郁悶！
盡力吧！
順便還是說兩句話：
1.有些書上分析的相當好了，我不想做畫蛇添足的人，所以有的地方我會適當省略，當然也不是說我總結的地方就是書上講的不好的地方，只是沒人有一套自己的理解方式，我用自己的話去總結了，當時也就是最適合我的知識！所以，建議大家多寫一些算法總結，你會體會到好處的！
2.而且我這個的性質是總結，不是對一個算法的具體講解，所以不先看書，大家應該讀不懂的，就比如下面，題目我就沒有貼出來，大家不看數，肯定就讀不懂，我的目的是大家看完書后，謝謝總結，或者看看別人寫的總結，說不定可以發現自己哪些地方理解錯了，哪些地方不理解，或是哪些地方值得探討。
建議先看看前言：http://www.wutianqi.com/?p=2298
這一次主要是分析15.1節的例子—裝配線調度問題。
題目有點長，首先得把題目讀懂。
這個例子書上花了6面紙的篇幅來詳細分析，由此可見其重要性。
談到DP,不得不說的就是暴力法，大家都知道，如果用暴力解決類似問題，一般時間復雜度都是非常非常的高，這個時候救世主DP就出來了，DP以避免了許多重復的計算，而大大降低了時間復雜度。
按照書上的四個步驟，我在這里提取一些重點，建議還是把P194~196這四步完整步驟看書上的分析。只有慢慢品味，你才會發現《算法導論》的美。
步驟一：
分析問題，比如一個底盤要到達S[1][j]，則有兩種情況，第一種是從S[1][j-1]到S[1][j]，第二種是從S[2][j-1]到S[1][j]。找出這兩者所花時間的最小，則就是S[1][j]所需時間的最小。
這就是有局部最優解求全局最優解。也就是說，一個問題的最優解包含了子問題的一個最優解。我們稱這個性質為最優子結構。這是是否可以應用DP的標志之一。
步驟二：
找出這個遞歸關系，由步驟一可以得到這個遞歸關系：
步驟三：
因為遞歸的關系，一般總是可以轉換為非遞歸的算法。
由已知量f1[1], f2[1]逐步推出未知量，推啊推，推啊推，最后就推到結果了~~~~
步驟四：
再由已知結果返回求路徑。
這一節最給力的就是這個例子以及相應的圖：
拿起筆，用書上給出的例子，分析這個圖！
以下是代碼：
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;
} |
最后還是要感嘆一下，《算法導論》講的真是棒極了，希望大家能靜下心把這一章節好好看看。
在我獨立博客上的原文：http://www.wutianqi.com/?p=2496
歡迎大家互相學習，互相進步！
posted @
2011-05-20 11:57 Tanky Woo 閱讀(1800) |
評論 (2) |
編輯 收藏第十四章我想放在后面再看，先擱下。希望大家總結的一些文章也能向我推薦下，大家互相學習。
首先，還是建議看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
其次，阿門，感謝老天送給了我們這么一本圣經，看了這一章，再次感受到了《算法導論》分析問題的精辟，強悍的魅力。Orz, Orz,各種Orz。
這一章講的是動態規劃，學算法的朋友，尤其是搞ACM的，對這個策略一定非常熟悉，所以這個算法網上的分析講解教程也是鋪天蓋地，大家可以多搜幾篇學習學習。
動態規劃(Dynamic Programming，簡稱DP)是通過組合子問題的解來解決問題的。
注意這里的programming不是指編程，而是指一種規劃。
因為DP用的太廣泛了，并且書上也花了很大的篇幅來講這一章，所以我也準備把這一章分幾篇來總結，并且我不按照書上的順序來總結，也不會全部用書上的例子。
這一章首先給出一些基礎的概念，然后給出一個最基礎入門的DP問題，三角形求值問題。
DP適用于子問題不是獨立的情況，這樣如果用分治法，也會作許多重復的工作，而DP只對子問題求解一次，將其結果保存在一張表中，從而避免了每次遇到各個子問題時重新計算的情況。
比較分治法于動態規劃的區別：
分治法：將問題劃分為一些獨立的子問題，遞歸的求解各子問題，然后合并子問題的解而得到原問題的解。
eg.
MERGE-SORT(A, p, r)
1 if p < r
2 then q ← |(p + r)/2|
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
動態規劃：適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題，鑒于會重復的求解各子問題，DP對每個問
題只求解一遍，將其保存在一張表中，從而避免重復計算。
DP算法的設計可以分為四個步驟：
①.描述最優解的結構。
②.遞歸定義最優解的值。
③.按自底而上的方式計算最優解的值。
④.由計算出的結果創造一個最優解。
下面來看看三角形求值這個問題：
將一個由N行數字組成的三角形，如圖所以，設計一個算法，計算出三角形的由頂至底的一條路徑，使該路徑經過的數字總和最大。
這是在我見過的DP題目中，算是最簡單的了，我相信就算沒有學過DP的也會。
將上圖轉化一下：
假設上圖用map[][]數組保存。
令f[i][j]表示從頂點(1, 1)到頂點(i, j)的最大值。
則可以得到狀態轉移方程：
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
此題既適合自頂而下的方法做，也適合自底而上的方法，
當用自頂而下的方法做時，最后要在在最后一列數中找出最大值，
而用自底而上的方法做時，f[1][1]即為最大值。
所以我們將圖2根據狀態轉移方程可以得到圖3：
最大值是30.
很簡單的DP題，代碼如下：
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
|
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
Description: 動態規劃之三角形求值問題
*/
#include <iostream>
using namespace std;
int map[6][6] =
{
{0, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 0, 0},
{0, 3, 8, 0, 0, 0},
{0, 8, 1, 0, 0, 0},
{0, 2, 7, 4, 4, 0},
{0, 4, 5, 2, 6, 5}
};
int f[6][6];
int _max(int a, int b)
{
if(a >= b)
return a;
return b;
}
int main()
{
memset(f, 0, sizeof(f));
for(int i=0; i<6; ++i)
f[5][i] = map[5][i];
for(int i=4; i>=1; --i)
for(int j=1; j<=i; ++j)
f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j];
for(int i=1; i<=5; ++i)
{
for(int j=1; j<=5; ++j)
{
cout.width(2);
cout << f[i][j] << " ";
}
cout << endl;
}
cout << f[1][1] << endl;
} |
結果如圖：
下一篇會將裝配線的調度。
在我獨立博客上的原文：http://www.wutianqi.com/?p=2484
歡迎大家互相學習，互相進步！
posted @
2011-05-20 07:27 Tanky Woo 閱讀(1748) |
評論 (0) |
編輯 收藏
摘要: 建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
這一章把前面三篇的代碼總結起來，然后推薦一些網上紅黑樹的優秀講解資源。
代碼：
1
2
3
...
閱讀全文
posted @
2011-05-12 16:33 Tanky Woo 閱讀(2049) |
評論 (1) |
編輯 收藏建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
這一篇是關于紅黑樹的結點刪除。
依然和上一篇的插入一樣，先用到了BST的刪除結點函數，然后做相應的調整。
不過，這里的調整思路頗為新穎。
還是來看看略微改變后的刪除結點函數：
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
| Node* RBTreeDelete(RBTree T, Node *z)
{
Node *x, *y;
// z是要刪除的節點,而y是要替換z的節點
if(z->lchild == NULL || z->rchild == NULL)
y = z; // 當要刪除的z至多有一個子樹，則y=z；
else
y = RBTreeSuccessor(z); // y是z的后繼
if(y->lchild != NULL)
x = y->lchild;
else
x = y->rchild;
// 無條件執行p[x] = p[y]
x->parent = y->parent;
if(y->parent == NULL)
T = x;
else if(y == y->parent->lchild)
y->parent->lchild = x;
else
y->parent->rchild = x;
if(y != z)
z->key = y->key;
if(y->color == BLACK)
RBDeleteFixup(T, x);
return y;
} |
注意代碼倒數第二和第三行，只有當后繼結點y的顏色是黑色時，才做調整。
由此，引導出幾個問題：
1.問：考慮為何當y的顏色是黑色時，才調整？當y的顏色是紅黑時，會不會破壞性質4？
答：這里我一開始糾結了，后來反復看了幾次BST的刪除，再算想通。在BST中，刪除結點z，并不是真的把z給移除了，其實刪除的不是z，而是y！因為z始終沒有動過，只是把y刪除了，然后把y的key賦值給z的key。所以，在紅黑樹中，z的顏色沒有變，依然符合紅黑性質。（這里我先開始理解為y->color也要賦值給z->color，汗。。。）
2.問：考慮y為黑色時，破壞了哪幾條紅黑性質？
答：當y是根時，且y的一個孩子是紅色，若此時這個孩子成為根結點。———>破壞了性質2
當x和p[y]都是紅色時。 ———>破壞了性質4
包含y的路徑中，黑高度都減少了。 ———>破壞了性質5
解決方法：
上一篇我解釋過，性質五涉及到了整棵樹，難以控制。
因此將x的顏色增加一重黑色，那么當:
①.x原先顏色為RED時——->x包含RED和BLACK兩顏色
②.x原先顏色是BLACK時—–>x包含BLACK, BLACK兩顏色。
此時性質5解決，但是又破壞了性質1.
接下來就是恢復性質1，2，4了。
將額外的一重黑色一直沿樹向上移，直到x是根或者是紅色結點。
看看具體的實現代碼：
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
| void RBDeleteFixup(RBTree &T, Node *x)
{
while(x != T && x->color == BLACK)
{
if(x == x->parent->lchild)
{
Node *w = x->parent->rchild;
///////////// Case 1 /////////////
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
LeftRotate(T, x->parent);
w = x->parent->rchild;
}
///////////// Case 2 /////////////
if(w->lchild->color == BLACK && w->rchild->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
///////////// Case 3 /////////////
if(w->rchild->color == BLACK)
{
w->lchild->color = BLACK;
w->color = RED;
RightRotate(T, w);
w = x->parent->rchild;
}
///////////// Case 4 /////////////
w->color = x->parent->color;
x->parent->color = BLACK;
w->rchild->color = BLACK;
LeftRotate(T, x->parent);
x = T;
}
}
else
{
Node *w = x->parent->lchild;
if(w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
RightRotate(T, x->parent);
w = x->parent->lchild;
}
if(w->lchild->color == BLACK && w->rchild->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if(w->lchild->color == BLACK)
{
w->rchild->color = BLACK;
w->color = RED;
LeftRotate(T, w);
w = x->parent->lchild;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->lchild->color = BLACK;
RightRotate(T, x->parent);
x = T;
}
}
}
x->color = BLACK;
} |
對于刪除的調整，共八種情況(左右對稱各四種)，這里在書上P175面講的很詳細，所以我也就不再畫圖了，大家可以自己拿起筆在草稿紙上畫一
在我獨立博客上的原文：http://www.wutianqi.com/?p=2449
歡迎大家互相討論，一起進步！
posted @
2011-05-11 11:52 Tanky Woo 閱讀(1871) |
評論 (1) |
編輯 收藏建議先看看前言：http://m.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
插入結點用到了上一次BST的插入函數(做了一點添加)，并且在此基礎上增加了保持紅黑性質的調整函數。
還是先看看插入函數：
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
|
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
|
和上一次的BST基本沒區別，只是添加了對新加結點z的顏色和子節點的處理。
這里把z的顏色設置為紅色，然后進行處理。
問：考慮為何把z的顏色設置為紅色？
答：個人認為如果設置為黑色，則破壞了性質五，而性質五關于黑高度的問題，涉及到了整棵樹，全局性難以把握，所以這里設置為紅色，雖然破壞了性質4，然是相對破壞性質5來說，更容易恢復紅黑性質。大家如果有不同的想法，也可以留言談談。
接下來，就是對整棵樹的調整了。
答：考慮插入z結點后，破壞的哪幾條紅黑性質？
答：破壞了性質2和性質4.
5條紅黑性質要熟記，我這里再貼出來：
1. 每個結點或是紅色，或是是黑色。
2. 根結點是黑的。
3. 所有的葉結點(NULL)是黑色的。（NULL被視為一個哨兵結點，所有應該指向NULL的指針，都看成指向了NULL結點。）
4. 如果一個結點是紅色的，則它的兩個兒子節點都是黑色的。
5. 對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。
所以我們要做的就是恢復性質2和性質4.
先來看看具體實現的代碼(這里只貼出部分代碼)：
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
|
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
///////////////////////
}
}
T->color = BLACK;
}
|
分三種情況，在代碼中已用Case 1, Case 2, Case 3標記出。
大致說下判斷情況：
1.首先讓一個指針y指向z的叔父結點(z是要刪除的結點)。
2.如果y的顏色是紅色，Case 1。則使z的父親結點和叔父結點的顏色改為黑，z的祖父結點顏色改為紅。然后讓z轉移到z的祖父結點。
3.當y的顏色是黑色時，
①.首先判斷z是否是其父親結點的右兒子，若是，則調整為左兒子(用旋轉)。
②.其次使z的父親結點顏色為黑，z的祖父結點顏色為紅，并以z的祖父結點為軸右旋。
具體我還是在草稿紙上畫出。。。(可憐買不起數碼相機，只能用手機拍了。。。)
（弱弱的問一句，看見網上有很多朋友做的一些代碼講解圖很給力，不知道大家有什么軟件嗎？求推薦。。。）
以下是插入的完整代碼：
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
|
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
Node *y = z->parent->parent->lchild;
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->lchild)
{
z = z->parent;
RightRotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
LeftRotate(T, z->parent->parent);
}
}
}
T->color = BLACK;
}
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
|
下一篇是關于紅黑樹的刪除。
posted @
2011-05-08 08:26 Tanky Woo 閱讀(1525) |
評論 (1) |
編輯 收藏