活动选择问题
活动选择问题问题可表述为“设\(S[0,1…n]\)为‘活动’的序列,每个‘活动’有开始、结束时间,\(S\)已按结束时间升序排序。规定所有‘活动’独占同一个教室,求出\(S\)中的‘活动’最多能安排多少个”。上图是其中一种\(S\)的例子。
设\(L\)是一个最优活动安排序列(已排序)。任取\(L[k]\),并用其划分序列\(L_1 = L[0,…,k-1],L_2=L[k+1,…]\)。然后设\(s_1\)是“\(L[k]\)开始前结束的\(S\)中的所有活动”,\(s_2\)是“\(L[k]\)结束后开始的\(S\)中的所有活动”。可发现如果把\(s_1,s_2\)作为原问题的输入,则\(L_1,L_2\)必可分别作为最优活动安排序列,否则\(L\)本身就不是原问题的最优解了。然后任取\(L_1[k_1]\)……可以发现上述结论是递归的。然后用这个性质去找最优解,先回到原问题上,其任意最优活动安排序列都符合“空序列,包含\(S[0]\),包含\(S[1]\),包含\(S[2]\)…”中的至少一种,如果符合的是空序列,那么解就是0,否则就遍历这些元素,设每次遍历到的元素是\(x\),然后用其划分\(S\)为“\(x\)开始前结束的\(S\)中的所有活动”,“\(x\)结束后开始的\(S\)中的所有活动”这两个序列,然后分别递归的求出它们的解并计做\(c_1,c_2\),然后求出\(c=c_1+1+c_2\),即放入\(x\)后的总活动数。每次遍历都会求一次\(c\),其中最大的那个就是解。… 阅读全文