從網易雲歌單說到貪心演算法

寫下這個字的時間點是23:53，是時候關掉電腦鑽進被窩戴上耳機聽會歌準備入睡了。或許是睡意還不太明顯，畢竟放假整天吃吃喝喝睡睡嘛，腦洞就閃進了一個問題，你想聽歌啊？聽多久？歌單怎樣選最好？

這樣，問題就來了。。。

睡前歌單

我網易雲歌單有539首歌，現在要從中選出一些今晚要聽的歌來組成睡前歌單，如果我給每首歌標上喜歡程度（真希望網易雲給加上這個功能），星級從一到五。而且聽歌時間不能多於一個小時。那，怎樣選才使自己最滿意呢？

顯然，衡量滿意度的標準就是選上的歌的喜歡程度的星級總和。記為S。

這個問題並沒有我文字描述的那樣無聊和簡單，暴力破解的方法當然可以把睡前歌單給弄出來，把所有歌都組合一遍，選出既滿足總時間長度小於一個小時又星級總和最高的不就搞定了嗎！？對啊，這樣當然可以，然而，算算運算量是多大吧，n首歌就是O(2^n)的運算量，我有539首歌就是2^539量級的運算量啊，全世界的人幫我算我今晚甚至這輩子歌也是聽不成了！

來來來，程序員入場，分析一下選歌過程吧。

總歌單是已經有的，記這個歌單為Like，歌單排列第i的歌表示為Like[ i ]，歌曲長度為Like[ i ].Length，星級為Like[ i ].Star，聽歌時間記為T（為簡化問題，假設時間的最少長度均為1s，即都是整數）。

現在，我們從歌單Like上的第一首歌來慢慢分析，第一首歌選不選呢？選的話，這首歌要佔去Like[1].Length的時間，而S增加了Like[1].Star，然後我們再考慮T-Like[1].Length時間下選不選Like[2]。不選的話，那跳過它，我們繼續考慮是否選Like[2]。咦，選或不選之後，我們好像又是要重複考慮選或不選哦，遞歸！最優子結構啊！動態規劃可以來解決這個問題！

動態規劃

動態規劃（Dynamic Programming），一般稱DP。

對於某一類問題，我們可以用DP方法來解決。《演算法導論》中是這樣說的

1.刻畫一個最優解的結構特徵

2.遞歸地定義最優解的值

3.計算最優解的值

4.利用計算出的信息構造一個最優解

演算法導論上的表述很是通俗，其實對於DP，核心是兩個東西，一個是狀態的定義，一個是確定狀態轉移方程。

狀態是什麼？就是問題本身，我們怎樣描述這個問題，就是在描述這個狀態。

狀態轉移方程是什麼？就是從問題到子問題的狀態轉移，對應於上面的第2點，一般形式就是遞歸方程。

一台計算機，歸根到底就是一台狀態機，我們把一個狀態輸入進去（比如2+2），狀態機通過某種方法，將狀態轉化為一個更易解的狀態（比如變成了1+1+1+1），依次下去，直到得出解。這個就不展開說了，可參見：有限狀態機-維基百科

回到我們的問題。現在我們來定義狀態，對於時間為T(單位秒)的聽歌時間，有N首歌，定義MaxS[N][T]：在前N首歌中選擇歌單，使其總長度不多於T，使S(星級總和)最大。最大值就記為MaxS[N][T]。對應我的歌單，最優解就可表示為MaxS[539][3600]，在前539歌中選擇歌單，使其總長度不多於3600秒，並使S最大。這裡我用了二維數組來表述，是為了說明在實際代碼中我們可以用二維數組來直接表達這個狀態。

接下來就是重中之重的狀態轉移方程，我先直接寫出來：

MaxS[N][T]=max{ MaxS[N-1][T] , MaxS[N-1][T-Like[i].Length] + Like[i].Star }

上面這鬼式子什麼意思呢？在N首歌中選擇，那第N首選不選？不選的話，則狀態變為MaxS[N-1][T]，因為現在我們要從前N-1首歌中選了，而可以聽的時間依然不變，並沒有減少。而選呢，那麼狀態變為MaxS[N-1][T-Like[i].Length]，因為依然要繼續從剩下的N-1首歌中選，可以聽的時間也減少了Like[i].Length，而S增加了Like[i].Star。選或不選哪個最大？最大的那個自然就等於MaxS[N][T]，狀態轉移方程就這樣出來了。

藉助狀態轉移方程，就可以動手碼代碼了。

其中核心偽代碼如下，初始條件是當i等於0時，MaxS均等於0。

for i=0 to N for j=0 to T MaxS[i][j]=MaxS[i-1][j] if j >= Like[i].Length and MaxS[i-1][j] < MaxS[i-1][T-Like[i].Length] + Like[i].Star MaxS[i][j] = MaxS[i-1][T-Like[i].Length] + Like[i].Star

上面的偽代碼表現的是自底向上的動態規劃演算法，時間複雜度顯然是O(N*T)。好像比O(2^N)少了好多了誒。

在上面偽代碼循環完成後，我們只要在後面加一個for循環，比較所有MaxS[i][j]和MaxS[i-1][j]，如果前者大於後者，則第i首歌是要選的，否則，第i首歌是不選的，這樣最優解就構造出來了，這個過程複雜度是O(N)，所以整個過程時間複雜度還是O(N*T)。

動態規劃一般之所以能大幅度減少運算時間，是因為其遞歸分解出來的子問題有很大一部分是重疊的，我們稱之為重疊子問題。在樸素演算法中，由於不對重疊子問題做處理，而是直接暴力運算，所以導致時間複雜度一般為指數型的，比如前面說到的組合來求解睡前歌單，複雜度為O(2*N)，而動態規劃則利用空間換時間的思想，將所有遇到的子問題的運算結果都保存下來，這樣，接下來的運算中，如果遇到了同樣的問題，則直接得到結果而不用再算一遍，所以一般能將時間複雜度降到多項式時間。能運用動態規劃來快速解決的問題一般具有兩個要素：最優子結構，重疊子問題。最優子結構保證了能用動態規劃演算法，重疊子問題保證了動態規劃演算法具有很好的時間複雜度。在上面的偽代碼中，我們自底向上，利用二維數組保存運算數據，類似的問題一般也是這樣做的，當後面想要獲取MaxS[i-1][j]的值的時候，我們已經計算好並只計算了一次這個值，直接給就行了，所以時間複雜度就大幅降低變成O(N*T)了，今晚就能算完開始聽了哈哈哈哈。。。。。

冷靜冷靜

好像哪裡不對，運用動態規劃能降低時間複雜度是因為具有大量的重疊子問題，在上面的偽代碼中，有哪些數組的值我們需要用到至少兩次的？？？好像並沒有啊！基本都只用到了一次啊！！！媽蛋問題又來了。

在上面的偽代碼中，只有在很巧合的情況下，某些數組的值會被用到兩次，比如某首歌的時間長度為0，或者其中一首歌的長度恰好為另外兩首歌的長度之和。其實，在寫狀態轉移方程的時候，我就覺得那式子的形式很眼熟了。現在細看，不就是背包問題的狀態轉移方程嗎，兩者是等價的好嗎。。。而背包問題是著名的NP完全問題。

NP完全問題

P類問題是指能在多項式時間內解決的問題，即O(n^k)，比如排序，我們能在O(nlgn)時間內解決。

NP類問題是指能在多項式時間內被證明的問題。

P明顯是NP的子集，進一步的，P是否是NP的真子集？即P是否等於NP？答案就不那麼顯而易見了，這個問題其實是當今最難的問題之一，你能給出答案，你就能走上人生癲瘋~

對於很多問題，如果我給出一個解，一般你都能在多項式時間內證明這個解是不是最優解，即NP類問題，然而，要在多項式時間內直接給出這個問題的最優解，就不是一個簡單的事情了，如果這個問題很難很難，目前並沒有多項式時間的解決演算法，我們稱之為NP完全問題（NP-Complete,NPC），你能在多項式時間內解決一個NP完全問題，就能在多項式時間內解決所有的NP完全問題，然後你的獎金能在北上廣深買很多很多好吃的，相信我:)。

我們的選歌單問題是NP完全問題嗎？很不幸，是的。選歌單問題和0-1背包問題是等價的，兩者的複雜度形式都是O(x*y)，看起來是多項式時間，其實並不是，通俗的理解，我們的歌曲數量是一首一首數的，那輸入數據規模就是一首一首增加的，而T是什麼鬼？是時間啊，誰說時間跟歌曲數量是多項式相關的？從而得出結論是多項式時間的？Naive!

造物主說，時間在計算機中是以二進位表示的，所以時間的輸入數據長度其實是lgT=B，所以O(N*T)=O(N*2^B)，哭了，是指數增長的。對於這種看起來是多項式時間演算法，實際並不是的，稱之為偽多項式時間演算法，同樣是偽多項式時間演算法的還有素數求解演算法等。

所以，又回到最初了，不管是直接組合暴力求解，還是動態規劃求解，時間複雜度均是非多項式的，所以能不能在睡前挑選完歌單，隨著聽歌時間長度和歌曲數目的增加，需要的挑選時間均是爆炸性增長的。然而，動態規劃依然是這個問題的最優解法之一，雖然同是指數增長，但是動態規劃的求解比組合暴力求解需要的時間還是大大減少的。兩者至少不是同一個量級的。所以對於背包問題，我們一般也是用動態規劃來求解的。這裡可以看出，利用重疊子問題從而可以空間換時間的性質並不是動態規劃的本質，僅僅是錦上添花而已，動態規劃的本質是利用最優子結構遞歸求解，專業的講是：對問題狀態的定義和狀態轉移方程的定義。

那，怎樣？有沒折中的方法？保證在不管時間長度和歌曲數量多少的情況下，我都能今晚就挑選出歌單。。。。

貪心演算法

可以用動態規劃，當然就能用貪心演算法了，演算法導論中是這樣表述的：

1.將最優化問題轉化為這樣的形式：對其做出一次選擇後，只剩下一個子問題需要求解。

2.證明做出貪心選擇後，原問題總是存在最優解，即貪心選擇總是安全的。

3.證明做出貪心選擇後，剩餘的子問題滿足性質：其最優解與貪心選擇組合即可得到原問題的最優解，這樣就得到了最優子結構。

又是啰里啰嗦的表述，簡單明了可以這樣說，對於一個問題，我們做出當下看起來最好的選擇，然後繼續求解剩下的唯一的子問題。

那選歌單的貪心演算法是怎樣的呢？

很容易想到，要想S值最大，則聽歌過程每一秒獲得的Star值應該儘可能的大。

對於歌曲Like[i]，聽它的時候，每一秒獲得的Star值是Like[i].Star / Like[i].Length。將這個值記為Like[i].StarPerSecond。

利用StarPerSecond進行從大到小排序，然後貪心演算法就啟動啦，排最前的肯定選啊，然後選第二的，然後選第三的，，，，直到聽歌時間用完了，挑選也就完成了。時間複雜度是O(n)，靠，多項式時間就這樣出來了。

那，這樣選出來的歌單是最優的嗎？

不是的，貪心演算法只能保證取得次優解而不能保證最優解。只有在踩到狗屎運的情況下，才能取得最優解。

我們這樣選出來的歌單，只能使最後取得的S接近最大值S，而不能保證取得S=S。

畢竟我的歌單Like有很多歌而且要聽一個小時，我就選貪心演算法吧，犧牲那麼點滿意度換取大量的時間值得了。

對於NP完全問題，我們一般也是採用近似演算法來取得多項式時間，而不強求一定要取得最優解。

至於為什麼不能保證S=S

證明，略:)

---------------------------------------------------------------------------------

原文轉自謝培陽的博客 2016-1-21

推薦閱讀：