建议先看看前言：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 阅读(1727) |
评论 (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 阅读(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 阅读(4083) |
评论 (2) |
编辑 收藏建议先看看前言：http://www.cppblog.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 阅读(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，就是从底层一层层的计算，然后在当层中选取最优，逐层最优以至总体最优。
其实这个还是多做一些题就好了(⊙ｏ⊙)，大家别认为我是做题控，其实说实在话，看N遍不如做一题，说白了，算法数学本一家，算法就是数学，走过高中的，都知道数学题得多做，尤其压轴题，看N遍不如做一遍，这个也是一样做几题就知道DP是神马东东了！
在我独立博客上的原文：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的标志之一。
步骤二：
找出这个递归关系，由步骤一可以得到这个递归关系：
步骤三：
因为递归的关系，一般总是可以转换为非递归的算法。
由已知量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 阅读(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行数字组成的三角形，如图所以，设计一个算法，计算出三角形的由顶至底的一条路径，使该路径经过的数字总和最大。
这是在我见过的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 阅读(1709) |
评论 (0) |
编辑 收藏
摘要: 建议先看看前言：http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html
这一章把前面三篇的代码总结起来，然后推荐一些网上红黑树的优秀讲解资源。
代码：
1
2
3
...
阅读全文
posted @
2011-05-12 16:33 Tanky Woo 阅读(2013) |
评论 (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 阅读(1828) |
评论 (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的祖父结点为轴右旋。
具体我还是在草稿纸上画出。。。(可怜买不起数码相机，只能用手机拍了。。。)
（弱弱的问一句，看见网上有很多朋友做的一些代码讲解图很给力，不知道大家有什么软件吗？求推荐。。。）
以下是插入的完整代码：
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 阅读(1471) |
评论 (1) |
编辑 收藏