算法期未复习重点.doc

《算法设计技巧与分析》复习重点
吴伟昶方世昌等译
第一章复习重点
、 sift_up 和sift_down、、
作业
(1)、、(a)、、、
(2)
第二章复习重点
作业
(1)(c)
(2)f(n)=2f(n-1)+n年,当n>=1时; f(0)=0
第五章复习重点
~
作业 、、、
第六章复习重点
、
作业 、、、
第七章复习重点
教学内容(以课件及实验为主)
最长公共子序列问题
0/1背包问题
树塔问题
最长递增子序列问题
硬币兑换问题
作业
(1)、、(a)(b)
第八章复习重点
教学内容(以课件为主)
(1)活动安排问题
(2)分数背包问题
作业
(1)
阅读与思考(时间复杂性的改进方法)
、
第十三章回溯法
教学内容(以课件为主)
图的着色问题
n后问题
哈密顿回路问题
分支限界法:旅行商问题
作业
(1)、n后的迭代算法、
阅读材料
数塔问题

设有一个三角形的数塔,如下图所示。求一从塔顶到塔底的路径,且该路径上顶点的值之和最大。
2. 最优子结构
n是n´n矩阵,顶点元素Cij,1£i,j£n,j为塔底,从塔底到塔顶i层的路径上顶点j的值之和为Vij,1£i,j£n,这里Vnn是n´n矩阵。若从塔底到塔顶i层的路径上有顶点j的值之和Vij最大,则Vij = max{ Vi+1j,Vi+1j+1}+ Cij。换言之,Vij是从塔底到塔顶i+1层的两条路径相关的顶点的值之和最大者加上Cij顶点的值。V11是原问题的最优值。即问题存在最优子结构。
3. 最优值递归关系
V[i,j]=
C[i,j] i=n,1£j£i
max{ V[i+1,j], V[i+1,j+1] } +C[i,j]} 1£i£n,1£j£i
当V[1,1]是原问题的最优值。
最长递增子序列问题
1. 问题描述
设是n个不同的整数的序列,L的递增子序列是这样一个子序列,其中且。求最大的m值。
2. 最优子结构
求以为最后元素的最长递增子序列,首先要找到且,。如果这样的元素存在,即以为最后元素的最长递增子序列存在。那么对所有,都有一个以为最后元素的最长递增子序列包含了以为最后元素的最长递增子序列,即问题存在
最优子结构。
3. 最优值递归关系
定义是一个表示L中以为最后元素的最长递增子序列的长度,则有:
即等于其之前所有的递增子序列的长度中最大的再加1。当时,。
硬币兑换问题
1. 问题描述
设有n种面值硬币,其中为单位货币。要求兑换数目为A的货币,使得兑换的硬币数最少。
2. 最优子结构
设C [i,J]表示从选择子集兑换数目为J货币所兑换的硬币数。于是,分两种情况讨论:
当J<时,选择子集不包括,则C [i,J]= C [i-1,J];
当J³时,选择子集包括,则C [i,J]= C [i,J-]+1。但最小硬币数是上述两情况的最少者。这一点说明了该问题具有最优子结构和子问题重