09年買的這本書，不過先開始一直沒怎么用，直到去年6月份左右開始搞ACM，才偶爾翻翻這本書。

這本書給我這樣的感覺：有時遇到一個算法，在網上找了很多相關資料，但是看完后還是有點迷茫，然后才想起《算法導論》，遇到翻開目錄，發現有相關的章節，于是去認真閱讀，頓時發現自己的很多問題都可以解決了。它就是這么一本書，也許你會把它當一本圣經來供養，但是當你認真閱讀后，你會發現你受益頗多。

于是，自從幾次問題通過《算法導論》解決后，我開始意識到，這是一個多么大的寶庫啊。它容納的目前常用的諸多算法，并且都給予了詳細解釋，圖文并茂，易于理解。

到目前為止，中間零散的看過一些章節。我有這么一個習慣，就是每學到一個算法，我都會把這個算法總結一下，我覺得雖然當時寫這個總結時有點占用時間，但是當你再溫故時，你只需要短短的5分鐘，就可以再次記住這個算法，并且通過以前總結的，你也許還可以發現不足，并改正。就像我之前有兩次都中斷了算法的學習，并且一斷就是幾個月，但是當我再次拾起算法時，我只需要看看我以前總結的筆記，就可以很快的拾起。在這里推薦下我的算法專題：http://www.wutianqi.com/sfzt.html

所以，這次我也準備把《算法導論》這本書好好總結一下，這樣當我總結時，我就可以知道哪些我徹底掌握了，因為如果我只掌握其表面內容，我是沒法用自己的話去總結。二是這樣大家通過各種搜索引擎搜到我的文章時，可以互相探討，并且發現哪些地方我理解錯了，因為我是非計科生，從大一到現在都是我自己一個人自學過來的，中間肯定會走一些彎路，對一些知識產生曲解，所以這樣也可以通過大家來改正我的錯誤，大家互相學習，互相探討，交一個可以討論學術的朋友，何樂而不為呢？

網上有些朋友推薦再遇到算法問題時可以把《算法導論》當字典來查，但是個人覺得，這本書讀多少遍都值得，所以完完整整的把這本書看一遍是必須的，以后再可以當一個工具書去查。所以推薦大家一起好好把《算法導論》學習下。

另外，我推薦每學一個算法，就去各個OJ（Online Judge）找一些相關題目做做，有時理論讓人很無語，分析代碼也是一個不錯的選擇。

對于接下來要寫的一些總結文章，我想做一些約定：

1.寫這個總結，我不能確定時間，也許一天總結一章，也許幾天總結一章，但是我不會斷的，鑒于書上有35章，我估計最快得兩個月的時間，最慢應該會花3個月在暑期之前搞定。(因為我還得準備考研，悲催啊。。。)

2.對于后序總結，我不會照搬書上去寫，我會盡量少寫書上已有的一些原話，我要寫的會是強調一些重點，以及書上講解過少的地方，我會找資料補充起來。

3.當然事情不是絕對的，對一些很重要的概念，算法等，我會根據書上及其他資料再寫一遍。

4.對于一些書上內容，當我借鑒時，我可能會直接從英文版的chm書上直接copy或者截圖(比如有特殊符號)。

5.因為我只看過部分章節，還有一些章節我也是小白，所以肯定會有一些地方自己也迷糊，大家發現我哪些地方講的不足，如果發現網上有講的詳細的，可以把網址通過留言告訴我，謝謝。

6.如果我文章里的哪些文字傷害了你的心靈，你可以留言告訴我，我會盡力去安慰你。（呵呵，開個玩笑），大家和諧討論，和諧學習，和諧共處

7.以后有需要補充的約定我還會再添加。。。

 

接下來，就讓我們大家一起來學習《算法導論》吧！

再廢話一句：

推薦論壇：C++奮斗樂園(C/C++/算法)：http://www.cppleyuan.com/

推薦QQ群：119154131（里面有一些高校的牛。。。加群請填寫ACM驗證）

http://www.wutianqi.com/?p=2298

我的獨立博客：http://www.wutianqi.com/
希望大家支持。
謝謝

原文鏈接：
http://www.wutianqi.com/?p=1028

---

          今天看了rakerichard的一篇文章，是寫的看了《瘋狂的程序員》后的一點感想。

 

          回憶起以前我看這本書，聯系自己學編程這一年多，感觸頗多。記得這本書剛出來時，我就在中關村圖書大廈買了一本。至今已經快一年了。故事情節依稀記得一點。

          里面講到了BOSS 絕的奮斗史，讀大學時和寢室一伙人到處折騰，給別人裝機子，去小公司找工作，以及后來的作為招聘人員去自己學校招員工，私下接外掛破解，和女友的坎坷經歷直到最后的分手。

          絕影的人生并不好走，雖然大學還未畢業就找到工作了，但是可以看出他的艱辛，經常熬夜趕項目；節假日不能陪家人，結果女友也要求分手了。

          我不知道該說什么好，別人都說嫁人要嫁程序員，程序員只關心電腦，不會在外面過那種花花綠綠的生活，這是褒義，還是貶義？也許只有說這話的人心里才清楚。

          我大學是讀自動化的，連我都不知道我為何要報自動化，我只知道，高考沒考到自己預想的分數，考了一個半吊子的分數：568分，而一本分數線是548.就這么高不高，低不低的。連我老爸當年讀的中南財經政法大學都讀不了，于是我也懶得管了，直接讓我父母報，結果第一志愿是北京化工大學的機械工程及其自動化，第二志愿是北京化工大學的自動化。最后第一志愿沒錄取，于是我到了北化的自動化系。雖然讀了兩年大學，我還不知道我這個專業到底是干啥的，只知道這個專業是一個萬金油，啥都行~~~

           大一剛進校，因為高考完在家天天玩網游，開學了還沒回過神來，別人都忙于互相認識，一起游覽北京的一些旅游景點，而我卻忙于在網吧與寢室兩地顛簸。那時剛開學，班級和學校有許多的活動，我一個都沒參加，記得開學就有學校和院的各個部門招人手，我那時沒認識到德育分的重要性，也沒有刻意去培養自己的結交能力(不過我的朋友還是非常多的~~在學校，許多人都和我很熟悉，因為我個人性格是比較活潑開朗的，且喜歡開玩笑，所以都比較隨和。)，但學校又要求每人都得報2項，所以其中一項我沒去，另外一項別人打電話過來了，我也說沒時間~~~（是不是很拽？）其實也不是不給他們面子，只是在我眼中，我不喜歡這些權勢及口頭上的較量，靠嘴皮子進去，一點用都沒，而且在我看來，這些東西都是無聊至極的，一群把自己當成官一樣來看待的，讓我感覺很不舒服。我喜歡那種靠自己真實實力較量的生活。并且在我看來，等工作了這些權勢競爭的生活多的是，在大學去浪費時間花在這上面太不值得了。就這么渾渾噩噩的一個學期快過完了，臨近寒假，發現別人雖然分一部分心思去弄學校各個部門的活，但是也確實培養了他們的個人能力，而我呢？除了會去網吧，還是去網吧。雖然那時成績不差，在班級30人中還能排在第10名。但是自己缺乏了其他獨特的能力。因為我接觸計算機很早，是從小學5年級開始的，所以我想到了從計算機這方面發展，剛開始對編程一竅不通，買了基本PS,FLASH,DW的書看，結果自己就是在美術細胞上太過于匱乏，始終弄不好，就這樣折騰了3個多月，最終放棄了，那時也知道了C語言，且知道下學期要學C語言，所以就提前自學了。我的編程生涯也就是從這個時候開始的（起步很晚~~）。

           剛開始學C語言，我就被吸引了，作為男生，我相信好多人都很YM那些開發軟件的人，我也不例外，而接觸了C語言，我才知道，這就是可以開發出軟件的東東，于是，我埋頭苦學…汗，其實也算不上苦學，就是把自己的課程都丟了，天天只看C語言的書，因為我不是計算機專業的，沒人教我，也沒人給我經驗，我就只能靠自己，計算機編程這方面的書都很貴的，還好有父母的經濟支持，這樣算一算，我10個月在買書上就花了2000元。我到現在都不知道怎么花的，反正牛人的書我都買了，還訂了好多雜志。記得看了譚老的《C語言程序》，《C Primer Plus》, 《The C Programming Language》 《C陷阱與缺陷》 《C專家編程》等等~~~太多了，我經常沒去上課，一個人抱著書和電腦去圖書館學。結果自己專業沒顧著，大二下學期還弄了個年級300人，倒數10幾名~~

           大二上學期我報了等級考試的三級數據庫，也順利的一次通過。呵呵，現在想來，也沒啥高興的，畢竟那些都是虛的，只需要靠2本書死記就過的，沒有一點技術含量，不值得高興。到了現在，數據庫的一些知識也快忘光了。

           大二上學期的暑假，我開始學習C++了。那時學了一段時間，寂寞了，于是建了幾個QQ群，在網上召集了一批C++愛好者一起交流，也就是那個時候，有了創辦一個論壇讓大家一起交流學習的想法。也就是在大二下學期開學后，隨著群的人越來越多，許多人也提議弄一個專門學習交流的地方，于是我買了空間和域名，辦了一個論壇。因為我覺得人生就要奮斗，我們學習編程，何嘗不是在為以后而奮斗，所以我給群，以及論壇取名叫C++奮斗樂園。域名我也選擇了cppleyuan。

           最開始接觸ACM不知道是在什么時候，應該實在大一下學期或大二上學期吧。那時就覺得這挺有趣的，但是也沒買書學習算法，就這么直接找上了POJ，經常把題目看懂就花了1個小時，然后做不出來，再分析別人代碼又是幾個小時~~~汗…后來覺得這東西不是我這種人弄的，就放棄了。不過還好，只是暫時放棄，在大二下學期開學后1個月，也就是2010年4月份左右吧。我又開始搞ACM了，因為學習C和C++也有一段時間了，對于編程也有了一定的認識，不再是那個初入編程大門，懵懵懂懂亂學的人了，我買了劉如佳老師的《算法學習經典入門》，《算法藝術與信息學競賽》，吳文虎老師的《世界大學生程序設計競賽》以及算法的圣經—-《算法導論》。就這么開始一個人在算法的海洋里探索了。也就是這個時候，因為自己對這方面有了解，并且覺得論壇不能只搞C++方面，所以我把論壇一部分分給了算法。畢竟算法是程序的靈魂。但是POJ對于我這個剛起步的小菜來說還是難了些。所以我開始轉向HDOJ了，7月10號注冊的。今天是8月17號，已經刷了210道水題了。我感覺，每AC一道題目，就感覺自己快樂了一分。也許這就是算法的魅力把，也可能這就是男人喜歡對事物的絕對掌控，感覺自己學懂了這個算法，就感覺自己多了一項能力。

           假期我給論壇弄了C/C++小項目和ACM刷題活動。當時我還到處找資料，花了一下午為C/C++小項目的第一個寫了一個詳細的流程圖，結果到最后無人問津，只有個別人做了，wujing的就做的很好，贊一個。不過還好，ACM刷題活動倒是很受歡迎，每天都有一批人和我一起刷，包括MiYu,大帥，蘿莉，timest,ac-quest等等。當然，amb教主我就不多說了，我只能YM。小白就是專門和我競爭的家伙。。。最近被他趕超了10題。郁悶。不過假期確實還是很開心的。畢竟結交了一群志同道合的朋友。

          現在假期也快結束了，8月20號返校，還得搬校區。

         看的書很多，想的也很多。喜歡思考編程，思考人生哲理。平時除了編程的書，我就最喜歡看自然科學和人生哲理了，《當下的力量》，《遇見心想事成的自己》，《秘密》這些書都很好，教會了我很多道理。感覺這些書就和算法一樣，講的都是內涵。人生就像編程，編的是人生，讓人生合理，規劃好人生，人生才能成功。

           最后，我想感謝C++奮斗樂園的各位斑竹，感謝假期陪我刷題的哥們，感謝支持我的論壇會員們。Orz

         以上算是發泄自己的情感，也算是傾述自己的經歷，或算是總結自己的經驗。不求能給大家什么幫助，只求大家能一起多交流點自己的經驗，互相借鑒，互相學習。
                                                                                                                                                                                                
                                                                                                                                                                          TankyWoo    
                                                                                                                                                                    2010年8月7號
我的博客：http://www.wutianqi.com/ 希望大家多多交流。

The Sieve of Eratosthens
愛拉托遜斯篩選法

---

（原創鏈接：http://www.wutianqi.com/?p=264）
思想：對于不超過n的每個非負整數P，刪除2*P, 3*P…，當處理

完所有數之后，還沒有被刪除的就是素數。

若用vis[i]==1表示已被刪除，則代碼如下：
—————————————————–
代碼一：

1memset(vis, 0, sizeof(vis));
2for(int i = 2; i <= 100; i++)
3    for(int j = i*2; j <= 100; j += i)
4        vis[j] = 1;

上面的代碼效率已經很高了。
但還可以繼續優化。
看一個改進的代碼：
——————————————————
代碼二：

 1int m = sqrt(double(n+0.5));
 2 
 3for(int i = 2; i <= m; i++)
 4    if(!vis[i])
 5    {
 6        prime[c++] = i;
 7        for(int j = i*i; j <= n; j += i)
 8        {
 9            vis[j] = 1;
10        }
11    }

——————————————————
先分析代碼一：
這個代碼就是簡單的將Eratosthenes篩選法描述出來。不用多說。
分析代碼二：
考慮幾點：
1.為何從i=2~m?
因為下面的j是從i*i開始的。
2.為何j從i*i開始？
因為首先在i=2時，偶數都已經被刪除了。
其次，“對于不超過n的每個非負整數P”， P可以限定為素數，
為什么？
因為，在 i 執行到P時，P之前所有的數的倍數都已經被刪除，若P

沒有被刪除，則P一定是素數。
而P的倍數中，只需看：
(p-4)*p, (p-2)*p, p*p, p*(p+2), p*(p+4)
（因為P為素數，所以為奇數，而偶數已被刪除，不需要考慮p*(p

-1)等）（Tanky Woo的程序人生）
又因為(p-4)*p 已在 (p-4)的p倍中被刪去，故只考慮：
p*p, p*(p+2)….即可
這也是i只需要從2到m的原因。
當然，上面 p*p, p*(p+2)…的前提是偶數都已經被刪去，而代碼

二若改成 j += 2*i ,則沒有除去所有偶數，所以要想直接 加2*i

。只需在代碼二中memset()后面加：
for(int i = 4; i <= n; i++)
if(i % 2 == 0)
vis[i] = 1;
這樣，i只需從3開始，而j每次可以直接加 2*i.
------------------------------------------------------
這里用代碼二給大家一個完整的代碼：

 1//版本二
 2//Author: Tanky Woo
 3//Blog: www.wutianqi.com
 4 
 5#include <stdio.h>
 6#include <string.h>
 7#include <math.h>
 8int vis[100];
 9int prime[100];
10int c = 0;
11int n;
12int main()
13{
14    scanf("%d", &n);
15    int cnt = 1;
16 
17    memset(vis, 0, sizeof(vis));
18    int m = sqrt(double(n+0.5));
19 
20    for(int i = 2; i <= m; i++)
21        if(!vis[i])
22        {
23            prime[c++] = i;
24            for(int j = i*i; j <= n; j += i)
25            {
26                vis[j] = 1;
27                //printf("%d\n", j);
28            }
29        }
30 
31    for(int i = 2; i < n; i++)
32    {
33        if(vis[i] == 0)
34        {
35            printf("%d ", i);
36            cnt++;
37            if(cnt % 10 == 0)
38                printf("\n");
39        }
40    }
41    printf("\ncnt = %d\n", cnt);
42    return 0;
43}

完畢。

---

歡迎大家和我交流。(我的博客:http://www.wutianqi.com/)

---

     摘要: 母函數（Generating function）詳解 （因為我是用Word寫好了貼上來的，不知為何圖片點插入不管用，這是原文：http://www.wutianqi.com/?p=596，大家可以直接去這里看。） 前段時間寫了一篇《背包之01背包、完全背包、多重背包詳解》，看到支持的人很多，我不是大牛，只是一個和大家一樣學習的人，寫這些文章的目的只是為了一是希望讓大家學的輕松，二是讓自己復...  閱讀全文

背包之01背包、完全背包、多重背包詳解

PS：大家覺得寫得還過得去，就幫我頂博客，謝謝。

首先說下動態規劃，動態規劃這東西就和遞歸一樣，只能找局部關系，若想全部列出來，是很難的，比如漢諾塔。你可以說先把除最后一層的其他所有層都移動到2，再把最后一層移動到3，最后再把其余的從2移動到3，這是一個直觀的關系，但是想列舉出來是很難的，也許當層數n=3時還可以模擬下，再大一些就不可能了，所以，諸如遞歸，動態規劃之類的，不能細想，只能找局部關系。

1.漢諾塔圖片

（引至杭電課件:DP最關鍵的就是狀態，在DP時用到的數組時，也就是存儲的每個狀態的最優值，也就是記憶化搜索）

要了解背包，首先得清楚動態規劃：

動態規劃算法可分解成從先到后的4個步驟：

1. 描述一個最優解的結構；

2. 遞歸地定義最優解的值；

3. 以“自底向上”的方式計算最優解的值；

4. 從已計算的信息中構建出最優解的路徑。

其中步驟1~3是動態規劃求解問題的基礎。如果題目只要求最優解的值，則步驟4可以省略。

背包的基本模型就是給你一個容量為V的背包

在一定的限制條件下放進最多(最少?)價值的東西

當前狀態→ 以前狀態

看了dd大牛的《背包九講》(點擊下載)，迷糊中帶著一絲清醒，這里我也總結下01背包，完全背包，多重背包這三者的使用和區別，部分會引用dd大牛的《背包九講》，如果有錯，歡迎指出。

(www.wutianqi.com留言即可)

首先我們把三種情況放在一起來看：

01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

比較三個題目，會發現不同點在于每種背包的數量，01背包是每種只有一件，完全背包是每種無限件，而多重背包是每種有限件。

——————————————————————————————————————————————————————————–：

01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均只有一件）第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

把這個過程理解下：在前i件物品放進容量v的背包時，

它有兩種情況：

第一種是第i件不放進去，這時所得價值為:f[i-1][v]

第二種是第i件放進去，這時所得價值為：f[i-1][v-c[i]]+w[i]

（第二種是什么意思？就是如果第i件放進去，那么在容量v-c[i]里就要放進前i-1件物品）

最后比較第一種與第二種所得價值的大小，哪種相對大，f[i][v]的值就是哪種。

（這是基礎，要理解！）

這里是用二位數組存儲的，可以把空間優化，用一位數組存儲。

用f[0..v]表示，f[v]表示把前i件物品放入容量為v的背包里得到的價值。把i從1~n(n件)循環后，最后f[v]表示所求最大值。

*這里f[v]就相當于二位數組的f[i][v]。那么，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重點！思考）
首先要知道，我們是通過i從1到n的循環來依次表示前i件物品存入的狀態。即：for i=1..N
現在思考如何能在是f[v]表示當前狀態是容量為v的背包所得價值，而又使f[v]和f[v-c[i]]+w[i]標簽前一狀態的價值？

逆序！

這就是關鍵！

1for i=1..N
2   for v=V..0
3        f[v]=max{f[v],f[v-c[i]]+w[i]};
4

分析上面的代碼：當內循環是逆序時，就可以保證后一個f[v]和f[v-c[i]]+w[i]是前一狀態的！
這里給大家一組測試數據：

測試數據：
10,3
3,4
4,5
5,6

這個圖表畫得很好，借此來分析：

C[v]從物品i=1開始，循環到物品3，期間，每次逆序得到容量v在前i件物品時可以得到的最大值。（請在草稿紙上自己畫一畫）

這里以一道題目來具體看看：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2602

代碼在這里：http://www.wutianqi.com/?p=533

分析：

具體根據上面的解釋以及我給出的代碼分析。這題很基礎，看懂上面的知識應該就會做了。

——————————————————————————————————————————————————————————–

完全背包：

完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

完全背包按其思路仍然可以用一個二維數組來寫出：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同樣可以轉換成一維數組來表示：

偽代碼如下：



for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-c[i]]+w[i]}

順序！

想必大家看出了和01背包的區別，這里的內循環是順序的，而01背包是逆序的。
現在關鍵的是考慮：為何完全背包可以這么寫？
在次我們先來回憶下，01背包逆序的原因？是為了是max中的兩項是前一狀態值，這就對了。
那么這里，我們順序寫，這里的max中的兩項當然就是當前狀態的值了，為何？
因為每種背包都是無限的。當我們把i從1到N循環時，f[v]表示容量為v在前i種背包時所得的價值，這里我們要添加的不是前一個背包，而是當前背包。所以我們要考慮的當然是當前狀態。
這里同樣給大家一道題目：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1114

代碼：http://www.wutianqi.com/?p=535

（分析代碼也是學習算法的一種途徑，有時并不一定要看算法分析，結合題目反而更容易理解。）

——————————————————————————————————————————————————————————–

多重背包

多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀態轉移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

這里同樣轉換為01背包：

普通的轉換對于數量較多時，則可能會超時，可以轉換成二進制（暫時不了解，所以先不講）

對于普通的。就是多了一個中間的循環，把j=0~bag[i]，表示把第i中背包從取0件枚舉到取bag[i]件。

給出一個例題：

題目：http://acm.hdu.edu.cn/showproblem.php?pid=2191

代碼：http://www.wutianqi.com/?p=537

因為限于個人的能力，我只能講出個大概，請大家具體還是好好看看dd大牛的《背包九講》。

暫時講完后，隨著以后更深入的了解，我會把資料繼續完善，供大家一起學習探討。(我的博客：www.wutianqi.com如果大家有問題或者資料里的內容有錯誤，可以留言給出，謝謝您的支持。)

原文下載地址：（Word版）
http://download.csdn.net/sour

個人原創，轉載請注明本文鏈接：http://www.wutianqi.com/?p=539