●第1章 算法概述1
1.1 算法與程序1
1.2 算法復雜性分析1
1.3 NP接近性理論4
算法分析題17
算法實現題17
第2章 遞歸與分治策略11
2.1 遞歸的概念11
2.2 分治法的基本思想16
2.3 二分搜索技術17
2.4 大整數的乘法18
2.5 Strassen矩陣乘法19
2.6 棋盤覆蓋20
2.7 合並排序22
2.8 快速排序24
2.9 線性時間選擇26
2.10 最接近點對問題29
2.11 循環賽日程表35
算法分析題236
算法實現題240
第3章 動態規劃46
3.1 矩陣連乘問題47
3.2 動態規劃算法的基本要素51
3.3 公共子序列54
3.4 優選子段和57
3.5 凸多邊形很優三角剖分62
3.6 多邊形遊戲65
3.7 圖像壓縮68
3.8 電路布線70
3.9 流水作業調度71
3.10 0-1背包問題74
3.11 很優二叉搜索樹79
算法分析題381
算法實現題382
第4章 貪心算法95
4.1 活動安排問題95
4.2 貪心算法的基本要素98
4.3 很優裝載100
4.4 哈夫曼編碼101
4.5 單源最短路徑105
4.6 最小生成樹108
4.7 多機調度問題111
算法分析題4113
算法實現題4113
第5章 回溯法120
5.1 回溯法的算法框架120
5.2 裝載問題125
5.3 批處理作業調度131
5.4 符號三角形問題133
5.5 n後問題135
5.6 0-1背包問題137
5.7 優選團問題140
5.8 圖的m著色問題142
5.9 旅行售貨員問題144
5.10 圓排列問題146
5.11 電路板排列問題148
5.12 連續郵資問題151
5.13 回溯法的效率分析153
算法分析題5155
算法實現題5156
第6章 分支限界法167
6.1 分支限界法的基本思想167
6.2 單源最短路徑問題170
6.3 裝載問題172
6.4 布線問題178
6.5 0-1背包問題181
6.6 優選團問題185
6.7 旅行售貨員問題187
6.8 電路板排列問題190
6.9 批處理作業調度193
算法分析題6197
算法實現題6198
第7章 隨機化算法207
7.1 隨機數208
7.2 數值隨機化算法209
7.3 舍伍德算法214
7.4 拉斯維加斯算法225
7.5 蒙特卡羅算法231
算法分析題7236
算法實現題7239
第8章 線性規劃與網絡流243
8.1 線性規劃問題和單純形算法243
8.2 優選網絡流問題256
8.3 最小費用流問題274
算法分析題8292
算法實現題8293
第9章 串與序列的算法306
9.1 子串搜索算法306
9.2 後綴數組與公共字串318
9.3 序列比較算法328
算法分析題9336
算法實現題9338
附錄A C++概要342
參考文獻349
