南京大学：《计算机问题求解》课程教学资源（课件讲稿）贪心算法

计算机问题求解一论题3-2 贪心算法 2016年09月07日

计算机问题求解 – 论题3-2 - 贪心算法 2016年09月07日

问题1： 你还记得什么是“Optimal Substructure吗？该结构特 性对求解最优解问题有什么肩 发？

Activity Selection Problem Suppose we have a set S=fa,a2....n of n proposed acivities that wish to use a resoure,such as a lecture hall,which can serve only one activity at a time.Each activity a has a start time s;and a finish time fi,where 0si<fi<oo.If selected,activity ai takes place during the half-open time interval [si,).Activities a and a are compatible if the intervals [si,)and [s,)do not overlap.That is,ai and aj are compatible if s ors In the activity-selection problem,we wish to select a maximum-size subset of mutually compatible activities. 一个样本输入 5678 10 8 8 2 12 99 11 14

Activity Selection Problem 一个样本输入：

问题2： Activity Selection问题是否具 有“最优子结构”，为什么？

S表示开始时间不早于活动a的结束时间，而 结束时间早于α的结束时间的所有活动的集合。 If we denote the size of an optimal solution for the set S by ci,],then we would have the recurrence cli,j]=cli,k]+ck,j+1. 假设我们知道其中包含活动a。 S中最多相互兼容的活动数 0 if Sij=0 ci,小= max {cli,k]+ck,j]+1 if Si ak∈SiU

Sij表示开始时间不早于活动ai的结束时间，而 结束时间早于aj的结束时间的所有活动的集合。 Sij中最多相互兼容的活动数 假设我们知道其中包含活动ak

动态规划解法 在上述递归关系中，a可以是S中任一活动，每选定一个 特定的a,则确定特定的子问题。动态规划方法按照合适 的次序解所有的子问题。 问题3： 是否有可能不必解所 有的子问题？

动态规划解法 在上述递归关系中，ak可以是Sij中任一活动，每选定一个 特定的ak , 则确定特定的子问题。动态规划方法按照合适 的次序解所有的子问题

问题4： 所谓“GREEDY”是指什 么？

Activity Selection:the Idea 要解的问题用Sk={a;∈S:≥f}表示，S是原始问题所给的 所有活动的集合，则原始问题为S: ■ Greedy方法： 口选择完成时间最早的活动，假设是a1; 口解子问题S Greedy可以指不同的“最”，但有的“最” 可以得到正确的解，有的“最”却未必！

Activity Selection: the Idea  要解的问题用 表示，S是原始问题所给的 所有活动的集合，则原始问题为S0 ;  Greedy方法：  选择完成时间最早的活动，假设是a1 ;  解子问题S1。 Greedy可以指不同的“最”，但有的“最” 可以得到正确的解，有的“最”却未必！

如何去“编程表达”这样的递归式？ RECURSIVE-ACTIVITY-SELECTOR

如何去“编程表达”这样的递归式？

GREEDY-ACTIVITY-SELECTOR(s,f) 1 n =s.length 2A={a1} 3k=1 4 for m 2 to n 问题5： 5 ifs[m]≥f[k] 6 A =AUam 为什么不需 7 k m 要递归？ 8 return A 问题6： 为什么代价是幾性的？