讓數學來告訴你高考作文的正確寫法：行囊到底該怎麼備？

antares 發表於  2016-06-07 22:25

　　「喏，這些東西你都可以帶。隨便你挑，可得仔細想想啊，前路漫漫，不帶今後就沒得用啦。」墨鏡黑衣男隨手指了指腳邊的一堆東西，品種繁多色彩各異，在陽光下折射出無數個閃耀的小光點，彷彿正在嘲諷我一籌莫展的樣子。「嗯，對了，這也是你們的作文題，要記得好好寫，有60分呢。」

　　

　　圖片來源：央視新聞微博

　　我苦笑著看了看手中的背包，背包就這麼點容量，要想走完剩下的路，非得想個辦法裝滿那些最有用的東西不可，或者換個說法，儘可能的讓我這個背包中的東西價值最大化。這是個問題。

　　身為一個數學學生，問題總是要解決的。首先我需要理清思路，給每個物品定個價值，很快就要用到的東西定個價值1，暫時用不上的物品通常也會永遠用不上，那麼定價為0，每天都要喝不喝會死的東西例如可樂…定價當然是10，總之先整理一番再說。比較幸運的一點是這個背包看起來採用了高彈性面料，對於面前的這堆小物件，我暫時不用考慮物品的體積問題。然則作為一隻長年不鍛煉身體的死宅，負重超過一定重量的話即使喝了可樂我還是會死，因此除了物品的價值，我還需要考慮的因素就只是它們的重量了。

　　還是擺脫這種無意義的敘述，讓我們轉換問題到一個更為標準的狀態好了：給定n種物品和一個彈性背包，物品i的重量是w_i，其價值為v_i，背包的承重上限為C。問應如何選擇裝入背包的物品（物品不能分割），使得裝入背包中物品的總價值最大?

　　坑爹，這不就是困擾了無數數學家與計算機科學家的背包問題么！

　　背包問題：只是看起來很簡單

　　你可能會認為，這種雞毛蒜皮問題有什麼好費腦筋的，用得著困擾么?

　　但是如果你換個角度，想想如果某活動贈送了一張1000元超市購物卡，顯然購物車裡的東西價格總和最好儘可能接近1000，又最好是每樣東西都是你最想要的。是不是感覺這個變種背包問題立刻變成了你經常困擾的問題了？推廣到投資應用，運貨裝船，這類問題顯然大家都時常遇到，是個非常重要的問題。

　　你可能會想：就算再重要又怎樣，反正我們有電腦嘛，讓電腦把每種可能的組合都算一遍，看看最優解不就可以了么。可是當我們有n個物品時，可能的組合就有2^n個，如果n是個稍微大一點的數，比如100，計算機需要計算10^30種可能性，目前常用的電腦計算速度也就每秒能算10^12次數量級次浮點運算， 這樣需要10^18秒左右，相當於10^13天，窮其一生，你居然算不出100件東西里能挑哪些來買，這你能忍？

　　日常買東西也就算了，遇到舉棋不定的時候憑著感覺走也不至於損失太大。但是重大商業決策，可就沒這麼隨便了；數學家更是不能忍，畢竟應用數學家的夢想就是開發出一套演算法來，不管你這個問題來多少變數，我都能用一致的辦法來解決。於是多年來，在這個問題上人們做了很多種研究，解法大致有兩條路。

　　

　　背包問題看似簡單，但實際上既重要又複雜。圖片來源：wikipedia

　　第一條路線：動態規劃演算法

　　當背包的重量限制不大的時候，是可以通過「動態規劃」求解的。動態規劃，簡單來說，就是把問題分解成不同的子問題分別求解，然後再合併子問題的解得到原問題的解——等等這繞口令哪裡簡單了啊？算了還是讓我來舉個例子吧。

　　假定我的負重限制是10kg，一共有10種物品需要考慮。這時我可以反著來思考，分成兩種可能性。

　　可能性1：最終我的背包里沒有可樂。那麼問題就變成了：如何把9種物品放進10kg背包中，使得最後結果最好。

　　可能性2：最終我的背包里是有可樂的。我知道可樂的重量是1kg，那麼背包就還剩9kg余量。那麼問題就變成了：如何把9種物品放進9kg背包中，使得最後結果最好。

　　兩種可能性里，價值更高的那個，當然就是我要的那個最優解。

　　但我還是不知道哪一種價值更高啊？沒事兒，我們把這兩種情況繼續分解下去，現在每種情況都按照有沒有餅乾來區分。這樣直到分解到最簡單的情況——比如背包負重只剩下1kg，一切都一目了然。這時候再反推回去，逐漸增加物品做遞歸，直到實際想要的重量限制10kg為止，就能算出最優解了。

　　

　　用動態規劃演算法解NP問題的一個簡單例子。圖片來源：allsyllabus.com

　　廢話這麼多，還是數學爽快。只要這一個公式：

　　f_n(W)=max{f_(n-1)(W)， f_(n-1)(W–w_n)+v_n}

　　這種演算法的缺點是所需要的計算時間複雜度為O(nW)。「時間複雜度」說白了就是一個演算法要花多少時間，不過因為演算法可以適用於很多問題，我們一般把它表達成問題本身大小的函數——O(nW)的意思就是，它所花的時間，和背包的負重上限W成正比。

　　當負重上限W很大時，這個演算法相對來說就比較慢，因此通常要做一些優化處理。例如，如果我們在最初的子問題中放入了 1kg的可樂，我特別喜歡它因此價值高達50。而在後續中我們放入了餅乾，餅乾2kg價值只有30，是不是覺得和可樂比起來，餅乾就沒什麼意義啦？那麼之後我們就不需要再考慮單獨餅乾了。但是我們也同時發現，如果同時放入可樂和餅乾，我們能用3kg的重量實現80的價值，那麼如果西瓜3kg價值10，那麼西瓜也不用考慮了。因此可以用捨棄劣質信息量的方法來簡化計算，讓動態規劃的演算法更為快一些。

　　但是僅僅如此也不夠，因此人們又開發了另一種思路來解決。

　　第二條路線：0-1規劃

　　另外一條路得回歸到我們剛剛吐槽過的遍歷思路，就是根據物品的重量老老實實求各種組合。顯然這是個線性的方程，並且變數要麼是0（不選這個物品）要麼是1（選這個物品），這樣就是一個0-1規劃。

　　如我們剛剛所說，這樣就有2^n種組合求最優解，在計算機中形成了一個二叉樹，需要做的是遍歷這棵樹的每一個點。顯然這樣會太麻煩，前面也說了，算起來會超慢的，因此需要想辦法剪去這棵樹的枝葉，讓找到最優解簡單一點。

　　以下是一些常用的思路。如果某種物品中重量大的超過上限，顯然包含它的組合都不用考慮了，這顯然是個最清晰直觀的簡化辦法。如果先把這些物品取整數的約束取消，即可以塞入0.x個物品，那麼就可以利用單位重量的價值最大這個原則求出一個解，再映射到和這個解相近的整數解上，這樣可通過不斷迭代來得到最後的答案。關於這類優化問題的演算法已經是數學系研究生級別的課題了，也就不再多敘述了。

　　一個NP完全問題；換言之，真的很難的問題

　　說到這裡，你是不是對背包問題的複雜度有了一個全新的認識？到底有多複雜呢？

　　來看這樣一個簡化一點，被稱作決定性問題的背包問題版本：給定背包，物品集和一個目標價值V，問能否找出一組物品使總價值至少達到目標價值。這個版本的背包問題，是1972年第一批被證明為NP完全（NP-Complete）的二十一個問題之一。

　　NP完全問題是什麼意思呢？

　　

　　NP問題在生活中其實無處不在：「-我們就想要價值正好15.05美元的前菜。這些論文或許可以幫到你：）」

　　「-……還有六桌等著點菜。」「-旅行推銷員問題！」圖片來源：xkcd

　　首先，如果對一個問題，有人回答了「是」並且給出了一組解，其他人可以簡單驗證這組解是否成立的話，這種問題叫做NP問題。

　　其次，我們希望在隨著問題本身規模的變大，它的「難度」——或者說，時間複雜度——不要增長得太過分。如果對於規模是n的問題，我要用指數增長的2^n的時間去解決，那這就太費時了，想想那個著名的國際象棋棋盤上放米粒的例子吧。一個理想的要求是，難度只按照多項式來增長，比如對於規模是n的問題，我只要n^2的時間就好。

　　最後，在NP問題中，有些問題特別的難，以至於如果我們能找到它的多項式解法，那麼所有其他NP問題就都有多項式解法了。這類最難的問題就被稱為NP完全問題。

　　而背包問題，就是一個NP完全問題。

　　NP完全問題中包含了其他很多實用且常見問題，如旅行推銷員問題，0-1規劃等等，因此NP問題是否能找到多項式複雜度的解法（P＝NP問題）是計算複雜度理論之中最重要的問題之一。美國克雷數學研究所於2000年懸賞過100萬美元的獎金呢。

　　所以現在也不要再抱怨每次出門前收拾行李時老是難以抉擇煩死人了，畢竟，我們可是從數學上證明，箱子里該裝什麼這個問題實在是太難了啦。 （編輯：Stellasun）