第1章 算法基本概念 1
1.1算法与程序 1
1.2算法复杂性分析 3
1.3算法分析实例 6
本章小结 10
思考与练习 10
第2章 常用的Java基础和数学方法 12
2.1 Java基础知识 12
2.2生成函数及其性质 26
2.3用特征方程求解递归方程 31
2.4用递推方法求解递归方程 36
2.5线性规划问题的可行域及最优性条件 40
本章小结 42
思考与练习 42
第3章 递归与分治 43
3.1递归算法 44
3.2分治法的基本思想 47
3.3二分搜索法 49
3.4大整数的乘法 50
3.5矩阵乘法 54
3.6合并排序 61
3.7快速排序 63
3.8最接近点对问题 68
3.9循环赛日程表 75
本章小结 80
思考与练习 80
第4章 动态规划 81
4.1动态规划问题 82
4.2动态规划问题的基本要素 83
4.3动态规划问题的一些例子 86
4.4动态规划的基本思想 90
4.5动态规划问题之最优二叉树问题 93
4.6最优路径 99
4.7矩阵连乘问题 102
4.8数字三角形问题 106
4.90-1背包问题 111
本章小结 118
思考与练习 118
第5章贪心算法 119
5.1贪心算法定义 119
5.2哈夫曼编码 123
5.3单源最短路径问题 125
5.4最小生成树问题 129
5.5背包问题 134
5.6贪心算法中的活动安排问题 140
本章小结 146
思考与练习 147
第6章回溯法 148
6.1回溯法的基本概念 148
6.2n皇后问题 153
6.30-1背包问题 156
6.4图的m着色问题 160
6.5旅行商问题 164
本章小结 168
思考与练习 168
第7章分支限界法 169
7.1分支限界法的基本思想 169
7.2最优装载问题 171
7.3最大团问题 179
7.4背包问题 183
7.5单源最短路径问题 189
本章小结 193
思考与练习 194
第8章线性规划与网络流问题 195
8.1线性规划问题和单纯形算法 195
8.2最大网络流问题 215
8.3预流推进算法 218
8.4最小费用流问题及消圈算法 220
本章小结 221
思考与练习 222
第9章概率算法 223
9.1随机数 224
9.2舍伍德算法 226
9.3 Monte Carlo算法 230
9.4拉斯维加斯算法 235
本章小结 237
思考与练习 238
第10章NP完全性理论 239
10.1基本概念 239
10.2 P类问题和NP类问题 241
10.3 NP完全性问题的定义与讨论 241
本章小结 247
思考与练习 247
第11章 近似算法 248
11.1近似算法的设计思想 248
11.2近似算法的性能 249
11.3顶点覆盖问题 250
11.4旅行商问题 255
本章小结 259
思考与练习 259
参考文献 260