中國數學建模-程式設計交流-貪婪演算法_如果我窮得還剩下一碗飯我也會讓你先吃飽全天下最好的東西都應該歸我所有，包括你！！ 先說喜歡我能死啊?別鬧，聽話。
有本事你就照顧好自己，不然就老老實實地讓我來照顧你！ 中國數學建模-程式設計交流-貪婪演算法
貪婪演算法
第 1 章貪婪演算法
雖然設計乙個好的求解演算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用於解決許多問題的演算法設計方法，你可以使用這些方法來設計演算法，並觀察這些演算法是如何工作的。一般情況下，為了獲得較好的效能，必須對演算法進行細緻的調整。但是在某些情況下，演算法經過調整之後效能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。
本章首先引入最優化的概念，然後介紹一種直觀的問題求解方法：貪婪演算法。最後，應用該演算法給出貨箱裝船問題、揹包問題、拓撲排序問題、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的求解方案。
1.1 最優化問題
本章及後續章節中的許多例子都是最優化問題（ optimization problem），每個最優化問題都包含一組限制條件（ c o
n s t r a i n t）和乙個優化函式（ optimization
function），符合限制條件的問題求解方案稱為可行解（ feasible
solution），使優化函式取得最佳值的可行解稱為最優解（optimal solution）。
例1-1 [ 渴嬰問題]
有乙個非常渴的、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n
種不同的飲料。根據以前關於這n
種飲料的不同體驗，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒採取如下方法為每一種飲料賦予乙個滿意度值：飲用1盎司第i
種飲料，對它作出相對評價，將乙個數值si 作為滿意度賦予第i 種飲料。
通常，這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要，但是不幸的是：具有最大滿意度值的飲料有時並沒有足夠的量來滿足此嬰兒解渴的需要。設ai是第i
種飲料的總量（以盎司為單位），而此嬰兒需要t 盎司的飲料來解渴，那麼，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？
設各種飲料的滿意度已知。令xi 為嬰兒將要飲用的第i 種飲料的量，則需要解決的問題是：
找到一組實數xi（1≤i≤n），使n åi = 1si xi 最大，並滿足：n åi=1xi =t 及0≤xi≤ai 。
需要指出的是：如果n åi = 1ai < t，則不可能找到問題的求解方案，因為即使喝光所有的飲料也不能使嬰兒解渴。
對上述問題精確的數學描述明確地指出了程式必須完成的工作，根據這些數學公式，可以對輸入/ 輸出作如下形式的描述：
輸入：n，t，si ，ai（其中1≤i≤n，n 為整數，t、si 、ai 為正實數）。
輸出：實數xi（1≤i≤n），使n åi= 1si xi 最大且n åi=1xi =t（0≤xi≤ai）。如果n åi = 1ai
在這個問題中，限制條件是n åi= 1xi =t 且0≤xi≤ai，1≤i≤n。而優化函式是n åi= 1si xi
任何滿足限制條件的一組實數xi 都是可行解，而使n åi= 1si xi 最大的可行解是最優解。
例1-2 [裝載問題] 有一艘大船準備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設第i
個貨箱的重量為wi（1≤i≤n），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多的貨物。
這個問題可以作為最優化問題進行描述：設存在一組變數xi ，其可能取值為0或1。如xi 為0，則貨箱i 將不被裝上船；如xi
為1，則貨箱i 將被裝上船。我們的目的是找到一組xi ，使它滿足限制條件n åi = 1wi xi ≤c 且x i î , 1 ≤i≤n。相應的優化函式是n åi= 1xi 。
滿足限制條件的每一組xi 都是乙個可行解，能使n åi= 1xi 取得最大值的方案是最優解。
例1-3 [最小代價通訊網路]
城市及城市之間所有可能的通訊連線可被視作乙個無向圖，圖的每條邊都被賦予乙個權值，權值表示建成由這條邊所表示的通訊連線所要付出的代價。包含圖中所有頂點（城市）的連通子圖都是乙個可行解。設所有的權值都非負，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優解是其中具有最小代價的生成樹。
在這個問題中，需要選擇乙個無向圖中的邊集合的子集，這個子集必須滿足如下限制條件：所有的邊構成乙個生成樹。而優化函式是子集中所有邊的權值之和。
1.2 演算法思想
在貪婪演算法（greedy
method）中採用逐步構造最優解的方法。在每個階段，都作出乙個看上去最優的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據稱為貪婪準則（greedy
criterion）。
例1-4 [找零錢]
乙個小孩買了價值少於1美元的糖，並將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2
5美分、1
0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入乙個硬幣。選擇硬幣時所採用的貪婪準則如下：
每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等於要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。
假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2
5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1
0美分的硬幣，然後是5美分的，最後加入兩個1美分的硬幣。
貪婪演算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證明採用上述貪婪演算法找零錢時所用的硬幣數目的確最少（見練習1）。
例1-5 [機器排程] 現有n 件任務和無限多台的機器，任務可以在機器上得到處理。每件任務的開始時間為si，完成時間為fi ，si
< fi 。[si , fi ] 為處理任務i 的時間範圍。兩個任務i，j 重指兩個任務的時間範圍區間有重疊，而並非是指i，j
的起點或終點重合。例如：區間[ 1，4 ]與區間[ 2，4 ]重疊，而與區間[ 4，7
不重疊。乙個可行的任務分配是指在分配中沒有兩件重疊的任務分配給同一臺機器。因此，在可行的分配中每台機器在任何時刻最多隻處理乙個任務。最優分配是指使用的機器最少的可行分配方案。
假設有n= 7件任務，標號為a 到g。它們的開始與完成時間如圖13-1a 所示。若將任務a分給機器m1，任務b 分給機器m2，. .
任務g分給機器m7，這種分配是可行的分配，共使用了七台機器。但它不是最優分配，因為有其他分配方案可使利用的機器數目更少，例如：可以將任務a、b、d分配給同一臺機器，則機器的數目降為五颱。
一種獲得最優分配的貪婪方法是逐步分配任務。每步分配一件任務，且按任務開始時間的非遞減次序進行分配。若已經至少有一件任務分配給某台機器，則稱這台機器是舊的；若機器非舊，則它是新的。
在選擇機器時，採用以下貪婪準則：根據欲分配任務的開始時間，若此時有舊的機器可用，則將任務分給舊的機器。否則，將任務分配給一台新的機器。
根據例子中的資料，貪婪演算法共分為n = 7步，任務分配的順序為a、f、b、c、g、e、d。第一步沒有舊機器，因此將a
分配給一台新機器（比如m1）。這台機器在0到2時刻處於忙狀態。在第二步，考慮任務f。由於當f 啟動時舊機器仍處於忙狀態，因此將f
分配給一台新機器(設為m2 )。第三步考慮任務b, 由於舊機器m1在sb =
數學建模競賽常用的演算法
1.蒙特卡羅方法 monte carlo方法,mc 該演算法又稱計算機隨機性模擬方法，也稱統計試驗方法。mc方法是一種基於 隨機數 的計算方法，能夠比較逼真地描述事物的特點及物理實驗過程，解決一些數值方法難以解決的問題。2.資料擬合 引數估計 插值等資料處理演算法 比賽中通常會遇到大量的資料需要處理...
數學建模交流講座總結
寧夏師範學院數學與電腦科學學院 數學建模交流座談會活動 總結主辦單位 數學與電腦科學學院團總支 承辦單位 數學興趣社 2013年11月23日 2013年11月20日下午三點整數學興趣社在學術報告廳舉行數學建模交流會並圓滿落下帷幕。本次座談會出席的嘉賓有數計學院副院長白龍老師 楊紀華 房琦貴老師 團總...
數學建模競賽經驗交流
1 時間和體力的問題 競賽中時間分配也很重要，分配不好可能完不成 所以開始時要大致做一下安排，不必分的太細，比如第一天做第一小題，第二天做第二小題，這樣反而會有壓力。開始階段不忙寫作，可以將一些小組討論的要點記錄下來，不要太工整，隨便一下，到第三天再開始寫 也不遲的。另外要說的就是體力要跟上，三天一...