算法期未复习重点.doc

《算法设计技巧与分析》复习重点
吴伟昶方世昌等译
第一章复习重点
算法 、 节 sift up 和 sifi_down、算法 、算法
作业 — —
、、(a)、、、
6/13 + n log nl0w
第二章复习重点
作业
(1) (c)
(2) f (n) =2f (n-1) +n 年，当 n〉=l 时;f (0) =0
第五章复习重点
〜
作业 、、、
第六章复习重点
算法 、
作业 、、、
第七章复习重点
(以课件及实验为主)
i.
最长公共子序列问题
ii.
0/1背包问题
iii.
树塔问题
iv.
最长递增子序列问题
V.
硬币兑换问题
作业
(1) 、、(a)(b)
第八章复习重点
教学内容(以课件为主)
活动安排问题
分数背包问题
作业
(1)
阅读与思考(时间复杂性的改进方法)
、

教学内容(以课件为主)
图的着色问题
n后问题
哈密顿回路问题
分支限界法：旅行商问题
作业
(1) 、n后的迭代算法、
阅读材料
（一）数塔问题
问题描述
设有一个三角形的数塔，如下图所示。求一从塔顶到塔底的路径，且该路径 上顶点的值之和最大。
最优子结构
设数塔的三角形为Cnn是nxn矩阵，顶点元素Cij, l<i,j<n, C“为塔顶，Cnj 为塔底，从塔底到塔顶i层的路径上顶点j的值之和为Vij, l<i,j<n,这里Vnn是 nxn矩阵。若从塔底到塔顶i层的路径上有顶点j的值之和Vij最大，则Vij = max（ Vi+ij, Vi+ij+i}+ Cijo换言之，Vij是从塔底到塔顶i+1层的两条路径相关的 顶点的值之和最大者加上Gj顶点的值。Vii是原问题的最优值。即问题存在最优 子结构。
最优值递归关系
V[i,j]=
i=n,l<j<i
C[i,j]
（二）最长递增子序列问题
问题描述
L的递增子序列是这样一个
设L = {aA,a2,---,an}是n个不同的整数的序列, 子序列 Lin={aki,ak2,---,akm},其中 kx<k2<■-<km 且％ <% <•••<%。求最大 的m值。
最优子结构
求以％为最后元素的最长递增子序列，首先要找到ai<aj且 i < j ,l<i < j o如果这样的兀素％存在，即以％为最后兀素的最长递增子序
列存在。那么对所有a,•,都有一个以勺为最后元素的最长递增子序列包含了以％ J J 1
为最后元素的最长递增子序列，即问题存在最优子结构。
最优值递归关系
定义L(j)是一个表小Z中以％为最后兀素的最长递增子序列的长度，则有:
L(j) = 1 + max｛L(z) | % < %且 1 < i < j｝
即匕(/)等于其之前所有的递增子序列的长度中最大的匕⑴再加lo当Z = 1
时，L(j) = 1 o
硬币兑换问题
问题描述
设有n种面值硬币P = ｛Pi，< p2