计算机问题求解一论题3-2 贪心算法 2020年09月22日
计算机问题求解 – 论题3-2 - 贪心算法 2020年09月22日
间题1： 你还记得什么是“Optimal Substructure”吗？该结构特 性对求解最优解间题有什么启 发？
Activity Selection Problem Suppose we have a set S =fa1,a2,...,an of n proposed activities that wish to use a resource,such as a lecture hall,which can serve only one activity at a time.Each activity ai has a start time si and a finish time fi,where 0<s<fi<oo.If selected,activity ai takes place during the half-open time interval [si,f).Activities a;and aj are compatible if the intervals [si,f)and [sj,fi)do not overlap.That is,ai and aj are compatible if si>fi or sj=fi.In the activity-selection problem,we wish to select a maximum-size subset of mutually compatible activities. re sorted 一个样本输入： 5678 10 8 8 2 11 14
Activity Selection Problem 一个样本输入：
问题2： Activity Selection问题是否具 有“最优子结构”，为什么？
S表示开始时间不早于活动a的结束时间，而结束时间早于α的结束 时间的所有活动的集合。 If we denote the size of an optimal solution for the set Sii by c[i,],then we would have the recurrence c,=ci,k个+ck,引+长 我们知道其中包含某活动4 S,中最多相互兼容的活动数 c=} if Sii=0 max fc[i,k]+c[k,j]+1 if Sij 这里的k怎么 表达？
Sij表示开始时间不早于活动ai的结束时间，而结束时间早于aj的结束 时间的所有活动的集合。 Sij中最多相互兼容的活动数 我们知道其中包含某活动ak 这里的k怎么 表达？