第1章 算法概述 1
1.1算法的概念 1
1.1.1算法与程序 1
1.1.2算法与数据结构 2
1.1.3算法表示的基本方法 3
1.1.4算法设计 6
1.2算法复杂性分析的方法 7
1.2.1两个算法的效率对比 8
1.2.2算法复杂性的度量 10
1.2.3复杂性的渐近性态及其阶 11
1.2.4复杂性渐近阶的重要性 14
1.2.5递归方程解的渐近阶的求法 16
小结 19
习题 20
第2章 分治与递归 22
2.1递归概述 22
2.2分治法概述 25
2.3分治法的应用 26
2.3.1排队购票问题 26
2.3.2整数划分问题 28
2.3.3“放苹果”问题 29
2.3.4第k选择问题 30
2.4典型问题分析 34
2.4.1红与黑 34
2.4.2循环赛日程表 35
2.4.3 0/1背包问题 36
2.5递归和递推 41
2.5.1递归和递推的比较 41
2.5.2“最少汽油过沙漠”问题 42
2.5.3整数划分递推设计 44
2.6递归的消除 48
小结 50
习题 50
第3章 贪心算法 52
3.1贪心算法概述 53
3.2活动安排问题 54
3.3背包问题 57
3.4贪心算法的两个基本要素 59
3.4.1贪心选择性质 59
3.4.2最优子结构性质 60
3.5典型问题分析 61
3.5.1最优装载问题 61
3.5.2删数问题 62
3.5.3均分纸牌 63
3.5.4拦截导弹问题 64
小结 66
习题 66
第4章 动态规划 68
4.1矩阵连乘问题 69
4.2凸多边形最优三角剖分 73
4.3最长公共子序列 75
4.4 DNA序列比对 79
4.5 0/1背包问题 81
4.6多段图问题 83
4.7数字三角形问题 85
4.8备忘录方法 89
4.9典型问题分析 90
4.9.1游船费问题 90
4.9.2航线设置 93
4.9.3复制书稿 95
4.9.4括号序列 97
小结 100
习题 100
第5章 搜索算法 102
5.1问题解空间的分析 102
5.1.1两种常见的树形问题解空间 102
5.1.2解空间的两种搜索方式 103
5.2回溯法概述 104
5.3分支限界法概述 106
5.4装载问题 108
5.4.1回溯法解装载问题 108
5.4.2分支限界法解装载问题 112
5.5 0/1背包问题 116
5.5.1回溯法解0/1背包问题 117
5.5.2分支限界法解0/1背包问题 119
5.6旅行售货员问题 124
5.6.1回溯法解旅行售货员问题 124
5.6.2分支限界法解旅行售货员问题 126
5.7典型问题分析 129
5.7.1子集和问题 129
5.7.2油田勘探问题 131
小结 134
习题 134
第6章 网络流和匹配 135
6.1最大流问题 135
6.1.1概念 135
6.1.2基本定理 138
6.1.3求最大流的标号法 138
6.2最小费用流问题 145
6.3匹配 150
6.3.1二部图 150
6.3.2匹配 152
6.4典型问题分析 155
6.4.1物流运输 155
6.4.2电力网络 158
6.4.3选择课程 160
6.4.4小行星 162
小结 163
习题 163
第7章 线性规划 166
7.1线性规划问题及其表示 166
7.2线性规划问题的数学形式 167
7.3一般问题转化为约束标准型 169
7.4线性规划的基、基础可行解 170
7.5单纯形法算法 173
7.5.1用消元法描述单纯形法算法 173
7.5.2单纯形算法的框架 176
7.6线性规划应用 180
小结 182
习题 182
参考文献 184