1 算法概述 1
1.1 算法概念 1
1.2 算法的复杂度 5
1.3 算法设计与分析的步骤 14
1.4 算法分析举例 17
1.5 算法描述语言简介 20
小结 25
习题 25
2 常用的数学工具 27
2.1 常用的函数和公式 27
2.2 用生成函数求解递归方程 30
2.3 用特征方程求解递归方程 35
2.4 用递推方法求解递归方程 40
3 递归与分治 45
3.1 递归技术概述 45
3.2 递归算法的例子 49
3.3 递归方程的建立与求解 52
3.4 递归消除 54
3.5 分治法概述 59
3.6 分治法举例 61
小结 87
习题 87
4 贪心法 89
4.1 货币兑付问题 89
4.2 贪心算法概述 90
4.3 背包问题 93
4.4 单源最短路径问题 97
4.5 最小花费生成树问题 102
4.6 最优装载 110
4.7 哈夫曼编码 113
小结 117
习题 117
5 动态规划 119
5.1 动态规划概述 119
5.2 0/1背包问题 125
5.3 最短路径 135
5.4 多矩阵乘积 141
5.5 最长公共子序列问题 145
小结 149
习题 149
6 回溯法 151
6.1 概述 151
6.2 背包问题 160
6.3 n皇后问题 166
6.4 图的着色问题 169
6.5 哈密尔顿回路问题 173
6.6 其他常见回溯法问题 176
6.7 回溯法的效率分析 183
小结 185
习题 185
7 分支限界法 187
7.1 概述 187
7.2 复杂的有限期作业调度问题 188
7.3 货郎担问题的分支限界法 190
7.4 其他分支限界问题 193
7.5 分支限界法与回溯法的比较 207
小结 208
习题 208
8 概率算法 210
8.1 概率算法概述 210
8.2 数值概率算法 212
8.3 蒙特卡罗算法 213
8.4 其他概率算法 215
小结 219
习题 219
9 NP问题 221
9.1 NP问题概述 221
9.2 P类与NP类问题 222
9.3 NP完全问题 225
9.4 一些典型的NP完全问题 229
小结 236
习题 236
参考文献 238