亚洲午夜久久久精品影院,久久精品无码午夜福利理论片,久久精品国产亚洲AV电影

《算法導論》學習總結 — 21.第16章貪心算法(1) 基礎入門1

建議先看看前言：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背包的程序去驗證這個結果。

下面是一個部分背包的小程序：

 
#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;
}

結果如圖：

Tanky Woo 標簽: Tanky Woo，貪心算法，算法導論

posted @ 2011-06-14 13:17 Tanky Woo 閱讀(1768) | 評論 (5) | 編輯收藏

《算法導論》學習總結 — 20.第15章動態規劃(5) 分析幾道DP題

看了下上一篇的日期，是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 Woo

在我獨立博客上的原文：http://www.wutianqi.com/?p=2559

歡迎大家互相學習，互相進步！

posted @ 2011-06-12 09:32 Tanky Woo 閱讀(1855) | 評論 (3) | 編輯收藏

談一下ACM的入門書籍及方法

首先說一下，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 閱讀(4116) | 評論 (2) | 編輯收藏

《算法導論》學習總結 — 19.第15章動態規劃(4) 案例之LCS

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

這個案例也比較簡單，最長公共子序列(LCS)，網上的分析非常多，給力啊！

按照上一篇總結所說的，找狀態轉移方程：

所以按照所給方程，寫代碼的工作就非常非常簡單輕松了：

/*
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

在我獨立博客上的原文：http://www.wutianqi.com/?p=2505

歡迎大家互相學習，互相進步！

posted @ 2011-05-26 18:55 Tanky Woo 閱讀(1503) | 評論 (2) | 編輯收藏

《算法導論》學習總結 — 18.第15章動態規劃(3) 基礎入門2

建議先看看前言：http://www.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是神馬東東了！

Tanky Woo 標簽: DP，動態規劃

在我獨立博客上的原文：http://www.wutianqi.com/?p=2500

歡迎大家互相學習，互相進步！

posted @ 2011-05-23 12:03 Tanky Woo 閱讀(1575) | 評論 (0) | 編輯收藏

《算法導論》學習總結 — 17.第15章動態規劃(2) 案例之裝配線調度

建議先看看前言：http://www.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]逐步推出未知量，推啊推，推啊推，最后就推到結果了~~~~

步驟四：

再由已知結果返回求路徑。

這一節最給力的就是這個例子以及相應的圖：

拿起筆，用書上給出的例子，分析這個圖！

以下是代碼：

/*
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 閱讀(1778) | 評論 (2) | 編輯收藏

《算法導論》學習總結 — 16.第15章動態規劃(1) 基本入門

第十四章我想放在后面再看，先擱下。希望大家總結的一些文章也能向我推薦下，大家互相學習。

首先，還是建議看看前言：http://www.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題，代碼如下：

/*
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 閱讀(1734) | 評論 (0) | 編輯收藏

《算法導論》學習總結 — 15. 第13章紅黑樹(4)

摘要: 建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html 這一章把前面三篇的代碼總結起來，然后推薦一些網上紅黑樹的優秀講解資源。代碼： 1 2 3 ... 閱讀全文

posted @ 2011-05-12 16:33 Tanky Woo 閱讀(2029) | 評論 (1) | 編輯收藏

《算法導論》學習總結 — 14. 第13章紅黑樹(3)

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

這一篇是關于紅黑樹的結點刪除。

依然和上一篇的插入一樣，先用到了BST的刪除結點函數，然后做相應的調整。

不過，這里的調整思路頗為新穎。

還是來看看略微改變后的刪除結點函數：

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是根或者是紅色結點。

看看具體的實現代碼：

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 閱讀(1847) | 評論 (1) | 編輯收藏

《算法導論》學習總結 — 13. 第13章紅黑樹(2)

建議先看看前言：http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html

插入結點用到了上一次BST的插入函數(做了一點添加)，并且在此基礎上增加了保持紅黑性質的調整函數。

還是先看看插入函數：

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.

先來看看具體實現的代碼(這里只貼出部分代碼)：

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的祖父結點為軸右旋。

具體我還是在草稿紙上畫出。。。(可憐買不起數碼相機，只能用手機拍了。。。)

（弱弱的問一句，看見網上有很多朋友做的一些代碼講解圖很給力，不知道大家有什么軟件嗎？求推薦。。。）

以下是插入的完整代碼：

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);
            }

下一篇是關于紅黑樹的刪除。

在我獨立博客上的原文：http://www.wutianqi.com/?p=2446

歡迎大家互相學習，互相討論！

posted @ 2011-05-08 08:26 Tanky Woo 閱讀(1494) | 評論 (1) | 編輯收藏

僅列出標題

常用鏈接

留言簿(8)

隨筆檔案

文章檔案

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜