发布时间 : 星期四 文章《算法分析与设计》期末考试复习题纲(完整版)更新完毕开始阅读
2. 用贪心算法求解活动安排问题/最小生成树问题/哈夫曼编码问题。 贪心算法求解活动安排问题
例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：
最小生成树问题 P103-P105
哈夫曼编码问题，前缀码二叉树表示法 例子：
图a:与固定长度编码对应的树(叶子高度一致) 图b:与可变长度编码对应的树(叶子高度不一致)
3. 用回溯法求解0-1背包问题/最优装载问题。 用回溯法求0-1背包问题。P133， 实例:n=5,M=50 N W P 1 15 30 2 5 12 2.4 1 15 30 2 3 25 44 4 27 46 5 30 50
P/W 2 N W P 2 5 12 1.76 1.70 1.67 3 25 44 4 27 46 5 30 50 (1).令bestp=0,将物体的序号按价值体积比排序结果是（2,1,3,4,5）
P/W 2.4 1.76 1.70 1.67 (2). 根据排序得到部分解(1,1,1,0)，估计当前部分解的价值b,86+(50-45)*1.67=94.3, b >bestp. (3). 继续向下搜索生成结点F，得到可行解(1,1,1,0,0)，得到价值为86，更新bestp=86(如图第3步)
第3步 第5步 第8步
(4). 回溯：沿E回溯到左孩子D，生成相应右孩子G，得到部分解( 1,1,0,1 ),此时b=93.1 b>bestp,可以生成右子树（第4步在第5步的基础上没有H和I的图形）
(5). 继续生成结点H,I，得到可行解( 1,1,0,1,0 ),价值为88，更新bestp=88(如图第5步) (6). 回溯H生成J，得到部分解( 1,1,0,0 ),估计部分解b=92>88（第6步在第8步的基础上没有K和L的图形）
(7). 继续生成结点K，得到可行解( 1,1,0,0, 1 ),价值为92，更新bestp=92（第7步在第8步的基础上没有L的图形）
(8). K是左孩子，生成其对应的右孩子L，得到可行解( 1,1,0,0,0) (如图第8步)
(9). 回溯,沿结点L向上回溯到结点B,生成结点M,得到部分解 (1,0), 估计部分解b=90<92,回溯（第9步在第10步的基础上没有N的图形） (10). 向上继续回溯生成结点N，得到部分解(0)，此时得到的b=74+10*(46/27) =91.03<92,回溯，此时已回到根结点，结束。最优解( 1,1,0,0, 1 ),价值为92. (如图第10步)
练习
n=8, M=110，
W=( 1, 11,21,23,33,43,45,55 ) P=(11,21,31,33,43,53,55,65 )
用回溯法求此0-1背包问题的最优解。
最优装载问题 P119 课件第P37- P54页 假定n= 4，w= [ 8 , 6 , 2 , 3 ]，c1 = c2 =12.
试根据改进后的最优装载算法找出最优装载量及相应的最优装载方案。 要求：
a) 列出问题的解空间。 b) 构造解空间树。
c) 根据递归回溯算法求出最优解和最优值。
六、算法设计题 使用贪心算法求解。 题型一： 开会问题：
某公司的会议很多，以至于全公司唯一的会议室不够用。现在给出这段时期的会议时间表，要求你适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议数最少。 解题算法:
template
void GS (int n, Type s[], Type f[], bool A[]) {
A[1]=false; int j=1; int sum=0;
for (int i=2;i<=n;i++) {
if (s[i]>=f[j]) { A[i]=false; j=i; } else {A[i]=true; sum++;} } } 题型二：
试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，写出该算法。先看看几个n比较小的例子，看能否从中找出规律：