随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 177791
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

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
posted @ 2011-04-09 12:13 Tanky Woo 阅读(3185) | 评论 (9)编辑 收藏



我的独立博客:http://www.wutianqi.com/
希望大家支持。
谢谢

posted @ 2010-09-24 09:22 Tanky Woo 阅读(226) | 评论 (2)编辑 收藏

原文链接:
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/ 希望大家多多交流。

posted @ 2010-08-17 11:33 Tanky Woo 阅读(2231) | 评论 (25)编辑 收藏

The Sieve of Eratosthens
爱拉托逊斯筛选法


(原创链接:http://www.wutianqi.com/?p=264[2:23]
思想:对于不超过n的每个非负整数P,删除2*P, 3*P…,当处理

完所有数之后,还没有被删除的就是素数。

若用vis[i]==1表示已被删除,则代码如下:
—————————————————–
代码一:

1memset(vis, 0sizeof(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, 0sizeof(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/)




posted @ 2010-08-04 13:55 Tanky Woo 阅读(1154) | 评论 (1)编辑 收藏
     摘要: 母函数(Generating function)详解 (因为我是用Word写好了贴上来的,不知为何图片点插入不管用,这是原文:http://www.wutianqi.com/?p=596,大家可以直接去这里看。) 前段时间写了一篇《背包之01背包、完全背包、多重背包详解》,看到支持的人很多,我不是大牛,只是一个和大家一样学习的人,写这些文章的目的只是为了一是希望让大家学的轻松,二是让自己复...  阅读全文
posted @ 2010-08-02 15:34 Tanky Woo 阅读(7154) | 评论 (8)编辑 收藏

背包之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

posted @ 2010-07-31 19:07 Tanky Woo 阅读(18285) | 评论 (11)编辑 收藏

建议先看看前言: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……

16_2

最后的结果是:

16_3

而如果按01背包,则结果是:

16_4

有兴趣的可以拿我那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;
}

结果如图:

16_1

Tanky Woo 标签: 
posted @ 2011-06-14 13:17 Tanky Woo 阅读(1726) | 评论 (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 标签:

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

欢迎大家互相学习,互相进步!

posted @ 2011-06-12 09:32 Tanky Woo 阅读(1834) | 评论 (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 阅读(4082) | 评论 (2)编辑 收藏

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

这个案例也比较简单,最长公共子序列(LCS),网上的分析非常多,给力啊!

按照上一篇总结所说的,找状态转移方程:

15_5

所以按照所给方程,写代码的工作就非常非常简单轻松了:

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的结果图:

15_6

又是一个给力的图,建议自己按照程序把这个图画出来.

另外,说到LCS,不得不说的是LIS(最长上升子序列),也是一个DP,我曾经总结过:

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

Tanky Woo 标签: 

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

欢迎大家互相学习,互相进步!

posted @ 2011-05-26 18:55 Tanky Woo 阅读(1487) | 评论 (2)编辑 收藏

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

这一节可以看到《算法导论》学习总结 — 16.第15章 动态规划(1) 基本入门的补充。

采用动态规划的最优化问题的两个要素:最优子结构重叠子问题

先看看最优子结构:

在第17篇总结时,装配线调度问题中,已经设计到了最优子结构,证明最优子结构问题可以用书上说的“剪贴技术”,即假设存在更优的解,来反正最优解矛盾。

再看看重叠子问题:

当一个递归算法不断的调用同一个问题时,我们说该最有问题包含“重叠子问题”。

上面这句话不好理解?

看看下面这个比较:

递归算法:自顶而下,对在递归树中重复出现的每个子问题都要重复解一次。

动态规划:自下而上,对每个只解一次。

结合第16篇总结的三角形求值例子,可以看得到,自下而上导致每个子问题只求解一次。

 

以上理论性有点强,我最开始学DP看的是HDOJ的课件,有兴趣的可以去看看。

在那里面,主要讲到了是找状态转移方程,在第16篇的三角形求值例子和第17篇的装配线调度例子,那些递归公式都是状态转移方程。

下面这段话好好理解:

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

动态规划的几个概念: 
阶段:据空间顺序或时间顺序对问题的求解划分阶段。 
状态:描述事物的性质,不同事物有不同的性质,因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。 
决策:根据题意要求,对每个阶段所做出的某种选择性操作。 
状态转移方程:用数学公式描述与阶段相关的状态间的演变规律。

动态规划是运筹学的一个重要分支,是解决多阶段决策过程最优化的一种方法。

所谓多阶段决策过程,是将所研究的过程划分为若干个相互联系的阶段,在求解时,对每一个阶段都要做出决策,前一个决策确定以后,常常会影响下一个阶段的决策。

动态规划所依据的是“最优性原理”。 
“最优性原理”可陈述为:不论初始状态和第一步决策是什么,余下的决策相对于前一次决策所产生的新状态,构成一个最优决策序列。

最优决策序列的子序列,一定是局部最优决策子序列。 
包含有非局部最优的决策子序列,一定不是最优决策序列。

动态规划的指导思想是:

在做每一步决策时,列出各种可能的局部解,之后依据某种判定条件,舍弃那些肯定不能得到最优解的局部解。这样,在每一步都经过筛选,以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝(从搜索角度看),效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优,不能保证全局最优,因为有些问题不符合最优性原理。

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

 

看见有人说递归就是DFS,而DP就是BFS,感觉有那么一点意思,对于DP,就是从底层一层层的计算,然后在当层中选取最优,逐层最优以至总体最优。

 

其实这个还是多做一些题就好了(⊙o⊙),大家别认为我是做题控,其实说实在话,看N遍不如做一题,说白了,算法数学本一家,算法就是数学,走过高中的,都知道数学题得多做,尤其压轴题,看N遍不如做一遍,这个也是一样做几题就知道DP是神马东东了!

 

Tanky Woo 标签: 

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

欢迎大家互相学习,互相进步!

posted @ 2011-05-23 12:03 Tanky Woo 阅读(1553) | 评论 (0)编辑 收藏

建议先看看前言:http://www.cppblog.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的标志之一。

步骤二

找出这个递归关系,由步骤一可以得到这个递归关系:

15_2

步骤三

因为递归的关系,一般总是可以转换为非递归的算法。

由已知量f1[1], f2[1]逐步推出未知量,推啊推,推啊推,最后就推到结果了~~~~

步骤四

再由已知结果返回求路径。

这一节最给力的就是这个例子以及相应的

15_3

拿起笔,用书上给出的例子,分析这个图!

以下是代码:

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 阅读(1748) | 评论 (2)编辑 收藏

第十四章我想放在后面再看,先搁下。希望大家总结的一些文章也能向我推荐下,大家互相学习。

首先,还是建议看看前言:http://www.cppblog.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行数字组成的三角形,如图所以,设计一个算法,计算出三角形的由顶至底的一条路径,使该路径经过的数字总和最大。

sanjiaoxing

这是在我见过的DP题目中,算是最简单的了,我相信就算没有学过DP的也会。

将上图转化一下:

sanjiaoxing2

假设上图用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:

sanjiaoxing3

最大值是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;
}

结果如图:

sanjiaoxing4

下一篇会将装配线的调度。

在我独立博客上的原文:http://www.wutianqi.com/?p=2484

欢迎大家互相学习,互相进步!

posted @ 2011-05-20 07:27 Tanky Woo 阅读(1708) | 评论 (0)编辑 收藏
     摘要: 建议先看看前言:http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html 这一章把前面三篇的代码总结起来,然后推荐一些网上红黑树的优秀讲解资源。 代码: 1 2 3 ...  阅读全文
posted @ 2011-05-12 16:33 Tanky Woo 阅读(2012) | 评论 (1)编辑 收藏

建议先看看前言:http://www.cppblog.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 阅读(1827) | 评论 (1)编辑 收藏

建议先看看前言:http://www.cppblog.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的祖父结点为轴右旋。

具体我还是在草稿纸上画出。。。(可怜买不起数码相机,只能用手机拍了。。。)

rbt_charu1

rbt_charu2

rbt_charu3

(弱弱的问一句,看见网上有很多朋友做的一些代码讲解图很给力,不知道大家有什么软件吗?求推荐。。。)

以下是插入的完整代码:

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

下一篇是关于红黑树的删除。


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

欢迎大家互相学习,互相讨论!

 

posted @ 2011-05-08 08:26 Tanky Woo 阅读(1470) | 评论 (1)编辑 收藏
仅列出标题  下一页