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