《算法导论》笔记－－动态规划解活动选择问题

　　假设某大学有一个活动室，我是这个活动管理员。某天，有6个社团都提出了使用活动室的要求，并告知了他们希望使用活动室的时间段（他们之间相互不知道对方的要求，因此时间安排是没有相互商量过的，可能有重叠）。活动室不能同时被两个以上社团使用。作为管理员，我无法每次都满足所有人的要求，但我想尽量提高活动室的使用率，那么，我如何选取某几项活动，使得活动室的使用时间最长呢？

　　如上图，假设上图是某一次这些社团的要求（假设0是正午12点），各颜色条分别是各个社团的使用时间计划。那么，我应该如何分配活动室呢？显然，如果给了社团5，其它社团就不能再使用该活动室了，这时活动室的使用时间是从2点到8点，共使用了6个小时。但这不是最长的使用时间组合。如果将活动室分配给1、3、4、6，那么除了4点到5点之间活动室是空的之外，其它时间活动室都被使用了，一共使用时间是8个小时。

（其实在《算法导论》一书的第16章第一节中，也提到一个活动选择问题。这里说的活动选择问题与书中的不一样。这两个问题要求不一样。那个问题将在贪婪算法相关的内容中讨论）

 

　　使用蛮力法，不会是一种好的方法。这一点就不过多论证了。

 

　　这是个最优化问题。我们探索下，会发现这个问题的最优解，是有可能表示成子问题最优解的递归解的。假设T_ij是一个从i点到j点的时间段，这个时间段内，最长的使用时间是S_ij。S_ij的计算中用到的活动，必须是要求整个活动时间被包括在T_ij中的，不能越过这个时间限。我们就称Vij是这样一个集合，其中包含了所有时间范围被完全包含在Tij范围内的活动。

假设对于i点到j点T_ij，如果i=j，那么很显然Sij就是0。如果i不等于j，那么最长使用使用时间S_ij可能是j-i个小时，也就是有一个活动从i点一直搞到j点，那么挺好，就选择这个活动就行了。但如果不存在这么长时间的活动，那么，我们可以试着把这个时间分成两个部分T_ik和T_kj，它们分别最长的使用时间是S_ik和S_kj。令S'=S_ik+S_kj，我们知道，当k从i到j依次取值时，可以得到各组不同的S_ik和S_kj，S_ij肯定是S'中取最大的那个值。为什么呢？因为如果没有一个在Tij时间内段的活动能充满整个Tij时间段的话，那么Vij内的任何一个活动单独放到Tij时间段内，那么在这个时间段的前端和后端，至少会出现一个空白的没被使用的时间，如下图：

　　所以，直感上看，就可以把空白的时间段取出来，看这个时间段内还能不能再按排一些活动。只要没有一个活动可以填满整个时间段，那么最大使用时间就是Vij内多个活动时间拼接成的。那么对于从i到j内的每一个时间点k，这个点左右两边Tik和Tkj内会分别安排一些活动（因为每个活动都是从整点开始到整点结束，而且各活动使用活动室的时间也不能重叠。但可能Vik或Vkj会为空），就分别能得到Sik和Skj。只要对每一个可能的k值进行检查，那么最大时间肯定就是其中的一个。

因此，我们可以得出S_ij的计算方法：

1. 如果i=j，则 S_ij=0
2. 否则，如果存在一个活动的时候长度恰好为T_ij，则S_ij=j-i
3. 否则，S_ij＝max{S_ik+S_ij} ，其中、k从i到j依次取值。

 

　　现在，我们已经得到了这个问题最优解的一个递归形式的解。递归式中包含了子问题的最优解。（关于子问题是否是最优解，可以用《算法导论》中的"剪切粘贴法"来考虑）。这是能用动态规划来解决的问题的第一个特征。

然后再看，如果我们根据这个递归直接翻译写出递归程序，那么，对于会出现很多重复的计算。比如，当我们计算S₀₉时，会用到S₀₁、S₀₂、S₀₃、S₀₄、......、S₀₇、S₀₈，再计算S₀₈时，又会用到S₀₁、S₀₂、S₀₃、S₀₄、......、S_07。以此类推，这个表达式中存在非常多的重复计算，计算量很大。嗯，有很多重叠的子问题，这是能用动态规划来解决的问题的第二个特征。

　　那么，根据动态规划的方法，就应该用从底向上的方法来解决这个问题，先计算小区间的值，并存储起来，然后再利用已经得到的小区间的值来计算大区间的值。最终得到原问题的最优解。如下图 

　　格子[i，j]表示从i点到j点，最大利用时间值是多少。灰掉的部分是无效值，因为此时i值大于j值，没有实际意思。这个表，我们从左到右计算每一列的值，就是用的从底向上的方法，最终可以地推出结果[0，9]的值是8.

　　在计算最大时间的过程中，将每次使得Sij最大时的K值记录下来，存储到K[i][j]中去，Sij得出来之后，就可以到出一个K[i][j]的表，根据这个表，可以得到如何不断地将时间划分成最优的两段，直至时间段内有活动充满该时间段，或是时间段内不存在任何活动。有了这个时间划分，我们就可以从这些时间段中分别相应的活动，这样，问题就最终得到了解决。

 

 （代码等续:)）

评论

2 楼 liyiwen007 2009-06-26  

canofy 写道

3. 否则，Sij＝max{Sik+Sij} ，其中、k从i到j依次取值。

这里应该是Sij＝max{Sik+Skj} ,应该是笔误吧～

确实确实~！！
没想到会有人看得这么细。想来应该是高手~！


谢谢你！

1 楼 canofy 2009-06-24  

3. 否则，Sij＝max{Sik+Sij} ，其中、k从i到j依次取值。

这里应该是Sij＝max{Sik+Skj} ,应该是笔误吧～