貪心演算法的一般解題策略

1. 五大常用演算法之一：貪心演算法

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，換句話說，當考慮做何種選擇的時候，我們只考慮對當前問題最佳的選擇而不考慮子問題的結果。這是貪心演算法可行的第一個基本要素。貪心演算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。 對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用貪心演算法求解的關鍵特徵。

值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。比如， 求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法 。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
貪心策略：選取價值最大者。反例：

W=30

物品：A B C

重量：28 12 12

價值：30 20 20

根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。

（2）貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。

（3）貪心策略：選取單位重量價值最大的物品。反例：

W=30

物品：A B C

重量：28 20 10

價值：28 20 10

根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候,優先裝重量小的,這樣的問題就可以解決.

所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）。

2. 程序員演算法基礎——貪心演算法

貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。

比如一道常見的演算法筆試題---- 跳一跳 ：

我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。

狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。

而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對於每個經過的盒子，不斷更新maxRight的值。

貪心的思考過程類似動態規劃，依舊是兩步： 大事化小 ， 小事化了 。
大事化小：
一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題；
小事化了：
從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的 向右能到達的最遠距離 ；

在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。

如果是動態規劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不對？ 平時我們找零錢有這么復雜嗎？
從貪心演算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然後再是5元、2元、1元紙幣。
從日常生活的經驗知道，這么做是正確的，但是為什麼？

假如我們把題目變成這樣，原來的策略還能生效嗎？

接下來我們來分析這種策略：
已知對於m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣（z<c），且紙幣張數更少（x+y+z<a+b+c），即是用更少5元紙幣得到最優解。
我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣；（因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張）
容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大於a+b+c。
由此我們知道不可能存在使用更少5元紙幣的更優解。
所以優先使用大額紙幣是一種正確的貪心選擇。

對於1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4；（1+1+1+7）
但如果只使用5元紙幣，則張數是2；（5+5）
在這種情況下，優先使用大額紙幣是不正確的貪心選擇。（但用動態規劃仍能得到最優解）

如果是動態規劃：
前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。
我們用 dp[i]表示前i秒能完成的任務數 ；
在計算前i秒能完成的任務數時，對於第j個任務，我們有兩種決策：
1、不執行這個任務，那麼dp[i]沒有變化；
2、執行這個任務，那麼必須騰出來(Sj, Tj)這段時間，那麼 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如說對於任務j如果是第5秒開始第10秒結束，如果i>=10，那麼有 dp[i]=max(dp[i], dp[5] + 1)； （相當於把第5秒到第i秒的時間分配給任務j）

再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情？我換一種描述方式：

我們自然而然會想到一個策略： 先把結束時間早的兼職給做了！
為什麼？
因為先做完這個結束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優化決策的能力。

這是一道 LeetCode題目 。
這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。
因為（前i個人的最少糖果數）這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那麼第i個人應該比第i+1個人多。
即是 這種狀態表示不具備無後效性。

如果是我們分配糖果，我們應該怎麼分配？
答案是： 從分數最低的開始。
按照分數排序，從最低開始分，每次判斷是否比左右的分數高。
假設每個人分c[i]個糖果，那麼對於第i個人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高）
但是，這樣解決的時間復雜度為 O(NLogN) ，主要瓶頸是在排序。
如果提交，會得到 Time Limit Exceeded 的提示。

我們需要對貪心的策略進行優化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。

再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；

這樣講過兩次遍歷，我們可以得到一個分配方案，並且時間復雜度是 O(N) 。

題目給出關鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河後，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關鍵原則： 應該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。

先不考慮空船回來的情況，如果有無限多的船，那麼應該怎麼分配？
答案： 每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。

再考慮只有一條船的情況，假設有A/B/C三個人，並且耗時A<B<C。
那麼最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長， 減少等待的原則 ）

如果有A/B/C/D四個人，且耗時A<B<C<D，這時有兩種方案：
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去； 總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發現差別僅在A+C和2B；
為何方案1、2差別里沒有D？
因為D最終一定要過河，且耗時一定為D。

如果有A/B/C/D/E 5個人，且耗時A<B<C<D<E，這時如何抉擇？
仍是從最慢的E看。（參考我們無限多船的情況）
方案1，減少等待；先送E過去，然後接著考慮四個人的情況；
方案2，減少浪費；先送E/D過去，然後接著考慮A/B/C三個人的情況；（4人的時候的方案2）

到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。
根據5個人的情況，我們可以推出狀態轉移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。

貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。

3. 求一個演算法(貪心演算法)

首先,無所謂哪裡密集哪裡不密集的說法,這是人為的區分,需要首先遍歷全部格子才能確定,是最慢的演算法,全部遍歷過了就可以得出最優的路線了.
既然用貪心演算法,為了思考方便,可以假設棋盤無窮大,演算法的目的是判斷下一步該往右走還是往下走，思想如下:
判斷當前格子右、下兩個相鄰的格子是否有金塊，情形如下：
1）如果一個有一個沒有，則往有金塊的格子走
2）如果都沒有或都有，則需要判斷往哪個方向走能更快的拾到下一個金塊，方法如下：
讓機器人假設地各往兩個方向走一步，然後對當前格子作判斷情形如下：
A)一個格子繼續走能拾到金塊，另一個不能，則上一步往該格子走
B)如果仍舊都有或都沒有，重復2）直到找到符合A）的情形。

假設棋盤是N*N個格子，則貪心演算法最壞的情形是要遍歷整個棋盤，比如只有第一個格子有金塊時，就需要遍歷整個棋盤才能確定走法。最好的情形也需要遍歷4*N個格子。
時間復雜度上來算的話，應該是O（nLogn）

4. [演算法] 貪心演算法證明思路

動態規劃和貪心演算法都需要問題具有最優子結構，但不同的是貪心 自頂向下 ，先做選擇再求解一個結果子問題，而動態規劃自底向上求解子問題，需要先求出子問題的最優解再做選擇。這是因為，動態規劃最優解有兩個子問題時，求解子問題 時有j-i-1種選擇，但貪心選擇特徵能夠使 其中一個子問題必定為空 ，這種子問題和選擇數目的減少使得子問題能夠自頂向下被解決。

a) 定義子問題空間，做出一個選擇從而產生一個或多個子問題。子問題空間的定義結合需要求解的目標和選擇後子問題的描述刻畫來考慮。
b) 利用「剪切-粘貼」證明作為最優解的組成部分的每個子問題的解也是它本身的最優解。如果子問題的解不是最優解，將其替換為對應的最優解從而一定能得到原問題一個更優的解，這與最初的解是原問題的最優解的前提假設矛盾，因此最優子結構得證。

貪心的本質是局部最優解能產生全局最優解，即產生兩個子問題 和 時，可以直接解決子問題 （在子問題 中，使用貪心策略選擇a作為局部最優解）然後對子問題 進行分解，最終可以合並為全局最優解。
因此，要證明貪心選擇性質只需要證明 存在一個最優解是通過當前貪心選擇策略得到的 ，反過來，即證明**通過非貪心策略得到的原問題的最優解中也一定包含局部最優解a。

定義通過非貪心策略的選擇可以得到的一個最優解A，將最優解中的元素和當前貪心策略會選擇的元素逐個交換後得到的解A'並不比
A差（假設貪心策略會選擇的元素在當前最優解中未被選擇，通過「剪切-粘貼」證明得到的仍是最優解），可以證明存在原問題的最優解可以通過貪心選擇得到。

5. (三) 貪心演算法

貪心演算法的思想非常簡單且演算法效率很高，在一些問題的解決上有著明顯的優勢。

假設有3種硬幣，面值分別為1元、5角、1角。這3種硬幣各自的數量不限，現在要找給顧客3元6角錢，請問怎樣找才能使得找給顧客的硬幣數量最少呢？

你也許會不假思索的說出答案：找給顧客3枚1元硬幣，1枚5角硬幣，1枚1角硬幣。其實也可以找給顧客7枚5角硬幣，1枚1角硬幣。可是在這里不符合題意。在這里，我們下意識地應用了所謂貪心演算法解決這個問題。

所謂貪心演算法，就是 總是做出在當前看來是最好的選擇(未從整體考慮) 的一種方法。以上述的題目為例，為了找給顧客的硬幣數量最少，在選擇硬幣的面值時，當然是盡可能地選擇面值大的硬幣。因此，下意識地遵循了以下方案：
（1）首先找出一個面值不超過3元6角的最大硬幣，即1元硬幣。
（2）然後從3元6角中減去1元，得到2元6角，再找出一個面值不超過2元6角的最大硬幣，即1元硬幣。
（3）然後從2元6角中減去1元，得到1元6角，再找出一個面值不超過1元6角的最大硬幣，即1元硬幣。
（4）然後從1元6角中減去1元，得到6角，再找出一個面值不超過6角的最大硬幣，即5角硬幣。
（5）然後從6角中減去5角，得到1角，再找出一個面值不超過1角的最大硬幣，即1角硬幣。
（6）找零錢的過程結束。
這個過程就是一個典型的貪心演算法思想。

貪心策略總是做出在當前看來是最優的選擇，也就是說貪心策略並不是從整體上加以考慮，它所做出的選擇只是在某種意義上的 局部最優解 ，而許多問題自身的特性決定了該問題運用貪心策略可以得到最優解或較優解。(註：貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。）

貪心演算法沒有固定的演算法框架，演算法設計的關鍵是 貪心策略的選擇 。選擇的貪心策略必須具備無後效性。

貪心策略 適用的前提 是：

嚴格意義上講，要使用貪心演算法求解問題，該問題應當具備以下性質：

注意 ：對於一個給定的問題，往往可能有好幾種量度標准。初看起來，這些量度標准似乎都是可取的，但實際上，用其中的大多數量度標准作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。

因此， 選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心 。

實際上，貪心演算法 適用的情況很少 。一般，對一個問題分析是否適用於貪心演算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。

最優解問題大部分都可以拆分成一個個的子問題(多階段決策問題)，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。

貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。

動態規劃方法代表了這一類問題的一般解法， 自底向上 構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。

而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始( 自頂向下 )，選擇最優的路，一直走到底就可以了。

一個問題分為多個階段，每個階段可以有n種決策，各個階段的決策構成一個決策序列，稱為一個策略。
這兩種演算法都是選擇性演算法，在進行決策的選擇時：

前提是這個問題得具有貪心選擇性質，需要證明(數學歸納法(第一、第二))，如果不滿足那就只能使用動態規劃解決。(一旦證明貪心選擇性質，用貪心演算法解決問題比動態規劃具有更低的時間復雜度和空間復雜度。)

從范疇上來看：
Greedy ⊂ DP ⊂ Searching （貪心是動規的特例）
即所有的貪心演算法問題都能用DP求解，更可以歸結為一個搜索問題，反之不成立。

貪心演算法所作的選擇可以依賴於以往所作過的選擇，但決不依賴於將來的選擇，也不依賴於子問題的解，這使得演算法在編碼和執行的過程中都有著一定的速度優勢。如果一個問題可以同時用幾種方法解決，貪心演算法應該是最好的選擇之一。但是貪心演算法並不是對所有的問題都能得到整體最優解或最理想的近似解，與回溯法等比較，它的適用區域相對狹窄許多，因此正確地判斷它的應用時機十分重要。

一步一步地進行，常 以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況 ，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。

它採用 自頂向下 ，以 迭代 的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以 貪心法不需要回溯 。

【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。

【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。

6. 貪心演算法的本質

1. 貪心法（Greedy Algorithm）定義

求解最優化問題的演算法通常需要經過一系列的步驟，在每個步驟都面臨多種選擇；

貪心法就是這樣的演算法：它在每個決策點作出在當時看來最佳的選擇，即總是遵循某種規則，做出局部最優的選擇，以推導出全局最優解（局部最優解->全局最優解）

2. 對貪心法的深入理解

（1）原理：一種啟發式策略，在每個決策點作出在當時看來最佳的選擇

（2）求解最優化問題的兩個關鍵要素：貪心選擇性質+最優子結構

①貪心選擇性質：進行選擇時，直接做出在當前問題中看來最優的選擇，而不必考慮子問題的解；

②最優子結構：如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質

（3）解題關鍵：貪心策略的選擇

貪心演算法不是對所有問題都能得到整體最優解的，因此選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

（4）一般步驟：

①建立數學模型來描述最優化問題；

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

③證明做出貪心選擇後：

1°原問題總是存在全局最優解，即貪心選擇始終安全；

2°剩餘子問題的局部最優解與貪心選擇組合，即可得到原問題的全局最優解。

並完成2°

3. 貪心法與動態規劃

最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

7. 數據結構之貪心演算法

貪婪演算法（Greedy）的定義：是一種在每一步選中都採取在當前狀態下最好或最優的選擇，從而希望導致結果是全局最好或最優的演算法。
貪婪演算法：當下做局部最優判斷，不能回退
（能回退的是回溯，最優+回退是動態規劃）
由於貪心演算法的高效性以及所求得答案比較接近最優結果，貪心演算法可以作為輔助演算法或解決一些要求
結果不特別精確的問題
注意：當下是最優的，並不一定全局是最優的。舉例如下：

有硬幣分值為10、9、4若干枚，問如果組成分值18，最少需要多少枚硬幣？
採用貪心演算法，選擇當下硬幣分值最大的：10
18-10=8
8/4=2
即：1個10、2個4，共需要3枚硬幣
實際上我們知道，選擇分值為9的硬幣，2枚就夠了
18/9=2
如果改成：

背包問題是演算法的經典問題，分為部分背包和0-1背包，主要區別如下：
部分背包：某件物品是一堆，可以帶走其一部分
0-1背包：對於某件物品，要麼被帶走（選擇了它），要麼不被帶走（沒有選擇它），不存在只帶走一部分的情況。
部分背包問題可以用貪心演算法求解，且能夠得到最優解。
假設一共有N件物品，第 i 件物品的價值為 Vi ，重量為Wi，一個小偷有一個最多隻能裝下重量為W的背包，他希望帶走的物品越有價值越好，可以帶走某件物品的一部分，請問：他應該選擇哪些物品？
假設背包可容納50Kg的重量，物品信息如下表：

將物品按單位重量 所具有的價值排序。總是優先選擇單位重量下價值最大的物品
按照我們的貪心策略，單位重量的價值排序： 物品A > 物品B > 物品C
因此，我們盡可能地多拿物品A，直到將物品1拿完之後，才去拿物品B，然後是物品C 可以只拿一部分.....

在不考慮排序的前提下，貪心演算法只需要一次循環，所以時間復雜度是O(n)

優點：性能高，能用貪心演算法解決的往往是最優解
缺點：在實際情況下能用的不多，用貪心演算法解的往往不是最好的

針對一組數據，我們定義了限制值和期望值，希望從中選出幾個數據，在滿足限制值的情況下，期望值最大。
每次選擇當前情況下，在對限制值同等貢獻量的情況下，對期望值貢獻最大的數據（局部最優而全局最優）
大部分能用貪心演算法解決的問題，貪心演算法的正確性都是顯而易見的，也不需要嚴格的數學推導證明
在實際情況下，用貪心演算法解決問題的思路，並不總能給出最優解

8. 貪心演算法幾個經典例子

[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。

要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

貪心演算法是很常見的演算法之一，這是由於它簡單易行，構造貪心策略簡單。但是，它需要證明後才能真正運用到題目的演算法中。一般來說，貪心演算法的證明圍繞著整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。

對於本例題中的3種貪心策略，都無法成立，即無法被證明。