天秤座的唐風(fēng)

　　假設(shè)某大學(xué)有一個(gè)活動(dòng)室，我是這個(gè)活動(dòng)管理員。某天，有6個(gè)社團(tuán)都提出了使用活動(dòng)室的要求，并告知了他們希望使用活動(dòng)室的時(shí)間段（他們之間相互不知道對(duì)方的要求，因此時(shí)間安排是沒(méi)有相互商量過(guò)的，可能有重疊）。活動(dòng)室不能同時(shí)被兩個(gè)以上社團(tuán)使用。作為管理員，我無(wú)法每次都滿足所有人的要求，但我想盡量提高活動(dòng)室的使用率，那么，我如何選取某幾項(xiàng)活動(dòng)，使得活動(dòng)室的使用時(shí)間最長(zhǎng)呢？

　

　　如上圖，假設(shè)上圖是某一次這些社團(tuán)的要求（假設(shè)0是正午12點(diǎn)），各顏色條分別是各個(gè)社團(tuán)的使用時(shí)間計(jì)劃。那么，我應(yīng)該如何分配活動(dòng)室呢？顯然，如果給了社團(tuán)5，其它社團(tuán)就不能再使用該活動(dòng)室了，這時(shí)活動(dòng)室的使用時(shí)間是從2點(diǎn)到8點(diǎn)，共使用了6個(gè)小時(shí)。但這不是最長(zhǎng)的使用時(shí)間組合。如果將活動(dòng)室分配給1、3、4、6，那么除了4點(diǎn)到5點(diǎn)之間活動(dòng)室是空的之外，其它時(shí)間活動(dòng)室都被使用了，一共使用時(shí)間是8個(gè)小時(shí)。

（其實(shí)在《算法導(dǎo)論》一書(shū)的第16章第一節(jié)中，也提到一個(gè)活動(dòng)選擇問(wèn)題。這里說(shuō)的活動(dòng)選擇問(wèn)題與書(shū)中的不一樣。這兩個(gè)問(wèn)題要求不一樣。那個(gè)問(wèn)題將在貪婪算法相關(guān)的內(nèi)容中討論） 

使用蠻力法，不會(huì)是一種好的方法。這一點(diǎn)就不過(guò)多論證了。

這是個(gè)最優(yōu)化問(wèn)題。我們探索下，會(huì)發(fā)現(xiàn)這個(gè)問(wèn)題的最優(yōu)解，是有可能表示成子問(wèn)題最優(yōu)解的遞歸解的。假設(shè)Tij是一個(gè)從i點(diǎn)到j(luò)點(diǎn)的時(shí)間段，這個(gè)時(shí)間段內(nèi)，最長(zhǎng)的使用時(shí)間是Sij。Sij的計(jì)算中用到的活動(dòng)，必須是要求整個(gè)活動(dòng)時(shí)間被包括在Tij中的，不能越過(guò)這個(gè)時(shí)間限。我們就稱Vij是這樣一個(gè)集合，其中包含了所有時(shí)間范圍被完全包含在Tij范圍內(nèi)的活動(dòng)。

假設(shè)對(duì)于i點(diǎn)到j(luò)點(diǎn)Tij，如果i=j，那么很顯然Sij就是0。如果i不等于j，那么最長(zhǎng)使用使用時(shí)間Sij可能是j-i個(gè)小時(shí)，也就是有一個(gè)活動(dòng)從i點(diǎn)一直搞到j(luò)點(diǎn)，那么挺好，就選擇這個(gè)活動(dòng)就行了。但如果不存在這么長(zhǎng)時(shí)間的活動(dòng)，那么，我們可以試著把這個(gè)時(shí)間分成兩個(gè)部分Tik和Tkj，它們分別最長(zhǎng)的使用時(shí)間是Sik和Skj。令S'=Sik+Skj，我們知道，當(dāng)k從i到j(luò)依次取值時(shí)，可以得到各組不同的Sik和Skj，Sij肯定是S'中取最大的那個(gè)值。為什么呢？因?yàn)槿绻麤](méi)有一個(gè)在Tij時(shí)間內(nèi)段的活動(dòng)能充滿整個(gè)Tij時(shí)間段的話，那么Vij內(nèi)的任何一個(gè)活動(dòng)單獨(dú)放到Tij時(shí)間段內(nèi)，那么在這個(gè)時(shí)間段的前端和后端，至少會(huì)出現(xiàn)一個(gè)空白的沒(méi)被使用的時(shí)間，如下圖：

 

    所以，直感上看，就可以把空白的時(shí)間段取出來(lái)，看這個(gè)時(shí)間段內(nèi)還能不能再按排一些活動(dòng)。只要沒(méi)有一個(gè)活動(dòng)可以填滿整個(gè)時(shí)間段，那么最大使用時(shí)間就是Vij內(nèi)多個(gè)活動(dòng)時(shí)間拼接成的。那么對(duì)于從i到j(luò)內(nèi)的每一個(gè)時(shí)間點(diǎn)k，這個(gè)點(diǎn)左右兩邊Tik和Tkj內(nèi)會(huì)分別安排一些活動(dòng)（因?yàn)槊總€(gè)活動(dòng)都是從整點(diǎn)開(kāi)始到整點(diǎn)結(jié)束，而且各活動(dòng)使用活動(dòng)室的時(shí)間也不能重疊。但可能Vik或Vkj會(huì)為空），就分別能得到Sik和Skj。只要對(duì)每一個(gè)可能的k值進(jìn)行檢查，那么最大時(shí)間肯定就是其中的一個(gè)。

因此，我們可以得出S_ij的計(jì)算方法：

1. 如果i=j，則 Sij=0
2. 否則，如果存在一個(gè)活動(dòng)的時(shí)候長(zhǎng)度恰好為T(mén)ij，則Sij=j-i
3. 否則，Sij＝max{Sik+Sij} ，其中、k從i到j(luò)依次取值。

現(xiàn)在，我們已經(jīng)得到了這個(gè)問(wèn)題最優(yōu)解的一個(gè)遞歸形式的解。遞歸式中包含了子問(wèn)題的最優(yōu)解。（關(guān)于子問(wèn)題是否是最優(yōu)解，可以用《算法導(dǎo)論》中的"剪切粘貼法"來(lái)考慮）。這是能用動(dòng)態(tài)規(guī)劃來(lái)解決的問(wèn)題的第一個(gè)特征。

然后再看，如果我們根據(jù)這個(gè)遞歸直接翻譯寫(xiě)出遞歸程序，那么，對(duì)于會(huì)出現(xiàn)很多重復(fù)的計(jì)算。比如，當(dāng)我們計(jì)算S₀₉時(shí)，會(huì)用到S₀₁、S₀₂、S₀₃、S₀₄、......、S₀₇、S₀₈，再計(jì)算S₀₈時(shí)，又會(huì)用到S₀₁、S₀₂、S₀₃、S₀₄、......、S_07。以此類推，這個(gè)表達(dá)式中存在非常多的重復(fù)計(jì)算，計(jì)算量很大。嗯，有很多重疊的子問(wèn)題，這是能用動(dòng)態(tài)規(guī)劃來(lái)解決的問(wèn)題的第二個(gè)特征。

那么，根據(jù)動(dòng)態(tài)規(guī)劃的方法，就應(yīng)該用從底向上的方法來(lái)解決這個(gè)問(wèn)題，先計(jì)算小區(qū)間的值，并存儲(chǔ)起來(lái)，然后再利用已經(jīng)得到的小區(qū)間的值來(lái)計(jì)算大區(qū)間的值。最終得到原問(wèn)題的最優(yōu)解。如下圖：
 

    格子[i，j]表示從i點(diǎn)到j(luò)點(diǎn)，最大利用時(shí)間值是多少。灰掉的部分是無(wú)效值，因?yàn)榇藭r(shí)i值大于j值，沒(méi)有實(shí)際意思。這個(gè)表，我們從左到右計(jì)算每一列的值，就是用的從底向上的方法，最終可以地推出結(jié)果[0，9]的值是8.

在計(jì)算最大時(shí)間的過(guò)程中，將每次使得Sij最大時(shí)的K值記錄下來(lái)，存儲(chǔ)到K[i][j]中去，Sij得出來(lái)之后，就可以到出一個(gè)K[i][j]的表，根據(jù)這個(gè)表，可以得到如何不斷地將時(shí)間劃分成最優(yōu)的兩段，直至?xí)r間段內(nèi)有活動(dòng)充滿該時(shí)間段，或是時(shí)間段內(nèi)不存在任何活動(dòng)。有了這個(gè)時(shí)間劃分，我們就可以從這些時(shí)間段中分別相應(yīng)的活動(dòng)，這樣，問(wèn)題就最終得到了解決。