第1章 算法概述
1.1 算法的概念
1.1.1 算法与程序
1.1.2 算法与数据结构
1.1.3 算法表示的基本方法
1.1.4 算法设计
1.2 算法复杂性分析的方法
1.2.1 两个算法的效率对比
1.2.2 算法复杂性的度量
1.2.3 复杂性的渐近性态及其阶
1.2.4 复杂性渐近阶的重要性
1.2.5 递归方程解的渐近阶的求法
小结
习题
第2章 分治与递归
2.1 递归概述
2.2 分治法概述
2.3 分治法的应用
2.3.1 排队购票问题
2.3.2 整数划分问题
2.3.3 “放苹果问题
2.3.4 第后选择问题
2.4 典型问题分析
2.4.1 红与黑
2.4.2 循环赛日程表
2.4.3 0/1背包问题
2.5 递归和递推
2.5.1 递归和递推的比较
2.5.2 “最少汽油过沙漠问题
2.5.3 整数划分递推设计
2.6 递归的消除
小结
习题
第3章 贪心算法
3.1 贪心算法概述
3.2 活动安排问题
3.3 背包问题
3.4 贪心算法的两个基本要素
3.4.1 贪心选择性质
3.4.2 最优子结构性质
3.5 典型问题分析
3.5.1 最优装载问题
3.5.2 删数问题
3.5.3 均分纸牌
3.5.4 拦截导弹问题
小结
习题
第4章 动态规划
4.1 矩阵连乘问题
4.2 凸多边形最优三角剖分
4.3 最长公共子序列
4.4 DNA序列比对
4.5 0/1背包问题
4.6 多段图问题
4.7 数字三角形问题
4.8 备忘录方法
4.9 典型问题分析
4.9.1 游船费问题
4.9.2 航线设置
4.9.3 复制书稿
4.9.4 括号序列
小结
习题
第5章 搜索算法
5.1 问题解空间的分析
5.1.1 两种常见的树形问题解空间
5.1.2 解空间的两种搜索方式
5.2 回溯法概述
5.3 分支限界法概述
5.4 装载问题
5.4.1 回溯法解装载问题
5.4.2 分支限界法解装载问题
5.5 0/1背包问题
5.5.1 回溯法解0/1背包问题
5.5.2 分支限界法解0/1背包问题
5.6 旅行售货员问题
5.6.1 回溯法解旅行售货员问题
5.6.2 分支限界法解旅行售货员问题
5.7 典型问题分析
5.7.1 子集和问题
5.7.2 油田勘探问题
小结
习题
第6章 网络流和匹配
6.1 最大流问题
6.1.1 概念
6.1.2 基本定理
6.1.3 求最大流的标号法
6.2 最小费用流问题
6.3 匹配
6.3.1 二部图
6.3.2 匹配
6.4 典型问题分析
6.4.1 物流运输
6.4.2 电力网络
6.4.3 选择课程
6.4.4 小行星
小结
习题
第7章 线性规划
7.1 线性规划问题及其表示
7.2 线性规划问题的数学形式
7.3 一般问题转化为约束标准型
7.4 线性规划的基、基础可行解
7.5 单纯形法算法
7.5.1 用消元法描述单纯形法算法
7.5.2 单纯形算法的框架
7.6 线性规划应用
小结
习题
参考文献