大概兩個(gè)星期以前，沙雕網(wǎng)友突然在沙雕群里發(fā)了一張沙雕草圖，原圖如下：

看到這張圖，我第一反應(yīng)是該沙雕群友這幾天看一個(gè)大概是叫asoul的vtb看瘋了，因?yàn)樗罱l(fā)的表情都變成了這個(gè)vtb的魔怔表情。但仔細(xì)一看這圖上居然是個(gè)算法題，于是寫期末大作業(yè)已經(jīng)同樣寫到魔怔的我決定試一試。

我們首先把這個(gè)魔怔的題干改成正常人看得懂的形式：小明一共上了n門課，其中第i門課的學(xué)分是vi，成績是ci。現(xiàn)要求找出課程集合，使得總學(xué)分最高，且加權(quán)均分不低于d。

看到這個(gè)題目，我們首先就會自然而然地想到，先把所有分?jǐn)?shù)>d的課都先拿走，畢竟這部分都是白賺來的學(xué)分，不拿白不拿。然后，在剩余所有分?jǐn)?shù)<d的課中，挑揀到盡量多的學(xué)分，同時(shí)在均分逐漸下降的過程中，保證最終不低于d。這里的第一反應(yīng)是采用分治法，即

getMaxTotal(int 當(dāng)前編號i, Set 已經(jīng)選擇的課程集合s) {

????if(i>n) return s的學(xué)分總和，直接結(jié)束

????if(選了i之后，均分仍然大于d) return getMaxTotal(i+1,s.add(i))和getMaxTotal(i+1,s))中的較大者

????else return?getMaxTotal(i+1,s))，因?yàn)榈趇個(gè)不能選了只能跳過

}

然后直接求getMaxTotal(1，空集)就能得出結(jié)果。

其實(shí)這個(gè)問題到這里已經(jīng)結(jié)束了，但這個(gè)算法有一個(gè)問題，就是時(shí)間復(fù)雜度為O(2^n)，因?yàn)檫@個(gè)算法實(shí)際實(shí)現(xiàn)了一個(gè)二叉選擇樹。盡管在樹的末端選擇會逐漸減少（均分已經(jīng)扣得差不多了），但并不會影響總的大O取值，而且一個(gè)“好的”題目的測試點(diǎn)是絕對不會給你這種不超時(shí)的機(jī)會的。這里要引用一句沙雕同學(xué)的語錄，“指數(shù)復(fù)雜度的算法多少都沾點(diǎn)腦癱”。為了避免我成為他口中的腦癱，這里的算法亟需改進(jìn)。

那么該怎么改進(jìn)呢？實(shí)際上在算法中，有類很出名的題目叫做0-1背包問題，大意是農(nóng)夫背著固定大小為V的包撿n塊石頭，每塊石頭的大小和價(jià)值都不同，最終在石頭大小總和不超過V的情況下獲取最大的總價(jià)值。這個(gè)問題猛一看和文章中的沙雕題很類似，但在這個(gè)題的解法中，算法通過維護(hù)一個(gè)“包剩余不同大小時(shí)，不同的n所能得到的最大價(jià)值”的n行V列的表，從而實(shí)現(xiàn)了數(shù)據(jù)的復(fù)用，通過浪費(fèi)一定的空間復(fù)雜度（把算好的數(shù)先記下來），使得時(shí)間復(fù)雜度降為O(V*n)。

但在本題中，“包”相當(dāng)于把所有分?jǐn)?shù)>d的課都先拿走后的平均分，而包的狀態(tài)并不像上述典型問題中那樣是連續(xù)的V種，而是一共有2^n種，這樣就完全繞回去了。實(shí)際上，我在剛看到這道題的時(shí)候就是卡在這里了，可能是因?yàn)楫?dāng)時(shí)正處于剛做完作業(yè)的半暈厥狀態(tài)。

然而，其實(shí)解決辦法也很簡單，就是把加權(quán)平均分中的Σci乘到上面去就好了，實(shí)際上是做了一個(gè)數(shù)字游戲。

Σ(vici)/Σ(ci)>=d
Σ(vici)-dΣ(vi)>=0
Σ(vi(ci-d))>=0
Σ(va(ca-d))>=Σ(vb(d-cb))，其中ab是把i分為了兩部分，a是分?jǐn)?shù)大于d的部分，b是分?jǐn)?shù)小于d的部分。此時(shí)式子的左半是背包，右半是石頭，并且背包和石頭的大小都是連續(xù)的。

至此，題目的解法應(yīng)該算是結(jié)束了，但最終留下了一個(gè)小問題，就是假如有些項(xiàng)目的分?jǐn)?shù)不是整數(shù)怎么辦。舉個(gè)栗子，假如有個(gè)nt老師給了一門課78.125分，那V的大小此時(shí)要相應(yīng)擴(kuò)大8倍。假如另一個(gè)老師給了80+π分，那就會讓整個(gè)算法的復(fù)雜度又回到O(2^n)的原點(diǎn)。但是，真的會有這樣的老師嗎？

以上。