貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。
比如一道常見的演算法筆試題---- 跳一跳 ：
我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。
狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。
而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用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]的值。
貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。
2. 演算法09-貪心演算法
貪心演算法與動態規劃的不同在於它對每個子問題的解決方案都作出選擇，不能回退。動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。
很多情況下，可以在某一步用貪心演算法，全局再加一個搜索或遞歸或動態規劃之類
貪心法可以解決一些最優化問題，如:求圖中的最小生成樹、求哈夫曼編碼等。然而對於工程和生活中的問題，貪心法一般不能得到我們所要求的答案。
一單一個問題可以通過貪心法來解決，那麼貪心法一般是解決這個問題的最好辦法。由於貪心法的高效性以及其所求得的答案比較接近最優結果，貪心法也可以用作輔助演算法或者直接解決一些要求結果不特別精確的問題。
當硬幣可選集合固定:Coins = [20,10,5,1],求最少幾個硬幣可以拼出總數。比如total=36。
36 - 20 = 16 20
16 - 10 = 6 20 10
6 - 5 = 1 20 10 5
1 - 1 = 0 20 10 5 1
前面這些硬幣依次是後面硬幣的整數倍，可以用貪心法，能得到最優解，
貪心法的反例
非整除關系的硬幣，可選集合:Coins = [10,9,1],求拼出總數為18最少需要幾個硬幣？
最優化演算法:9 + 9 = 18 兩個9
貪心演算法:18 - 10 = 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0 八個1
簡單地說，問題能夠分解成子問題來解決，子問題的最優解能遞推到最終問題的最優解。這種子問題最優解成為最優子結構。
貪心演算法與動態規劃的不同在於它對每個子問題的最終方案都作出選擇，不能回退。
動態規劃則會保存以前的運算結果，並根據以前的結果對當前進行選擇，有回退功能。
假設你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多隻能給一塊餅干。
對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅乾的最小尺寸；並且每塊餅干 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以將這個餅干 j 分配給孩子 i ，這個孩子會得到滿足。你的目標是盡可能滿足越多數量的孩子，並輸出這個最大數值。
示例 1:
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋:
你有三個孩子和兩塊小餅干，3個孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干，由於他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應該輸出1。
示例 2:
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋:
你有兩個孩子和三塊小餅干，2個孩子的胃口值分別是1,2。
你擁有的餅干數量和尺寸都足以讓所有孩子滿足。
所以你應該輸出2.
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
設計一個演算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
隨後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之後再將它們賣出。
因為這樣屬於同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。
給定一個非負整數數組 nums ，你最初位於數組的 第一個下標 。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最後一個下標。
示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然後再從下標 1 跳 3 步到達最後一個下標。
示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最後一個下標。
給定一個非負整數數組，你最初位於數組的第一個位置。
數組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數到達數組的最後一個位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最後一個位置的最小跳躍數是 2。
從下標為 0 跳到下標為 1 的位置，跳 1 步，然後跳 3 步到達數組的最後一個位置。
說明:
假設你總是可以到達數組的最後一個位置。
移動下標只要遇到當前覆蓋最遠距離的下標，直接步數加一，不考慮是不是終點的情況。
想要達到這樣的效果，只要讓移動下標，最大隻能移動到nums.size - 2的地方就可以了。
因為當移動下標指向nums.size - 2時：
如果移動下標等於當前覆蓋最大距離下標， 需要再走一步（即ans++），因為最後一步一定是可以到的終點。（題目假設總是可以到達數組的最後一個位置），如圖：
如果移動下標不等於當前覆蓋最大距離下標，說明當前覆蓋最遠距離就可以直接達到終點了，不需要再走一步。如圖：
機器人在一個無限大小的 XY 網格平面上行走，從點 (0, 0) 處開始出發，面向北方。該機器人可以接收以下三種類型的命令 commands ：
-2 ：向左轉 90 度
-1 ：向右轉 90 度
1 <= x <= 9 ：向前移動 x 個單位長度
在網格上有一些格子被視為障礙物 obstacles 。第 i 個障礙物位於網格點 obstacles[i] = (xi, yi) 。
機器人無法走到障礙物上，它將會停留在障礙物的前一個網格方塊上，但仍然可以繼續嘗試進行該路線的其餘部分。
返回從原點到機器人所有經過的路徑點（坐標為整數）的最大歐式距離的平方。（即，如果距離為 5 ，則返回 25 ）
注意：
北表示 +Y 方向。
東表示 +X 方向。
南表示 -Y 方向。
西表示 -X 方向。
示例 1：
輸入：commands = [4,-1,3], obstacles = []
輸出：25
解釋：
機器人開始位於 (0, 0)：
在檸檬水攤上，每一杯檸檬水的售價為 5 美元。
顧客排隊購買你的產品，（按賬單 bills 支付的順序）一次購買一杯。
每位顧客只買一杯檸檬水，然後向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。
注意，一開始你手頭沒有任何零錢。
如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
示例 1：
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那裡，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那裡，我們收取一張 10 美元的鈔票，並返還 5 美元。
第 5 位顧客那裡，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由於所有客戶都得到了正確的找零，所以我們輸出 true。
示例 2：
輸入：[5,5,10]
輸出：true
示例 3：
輸入：[10,10]
輸出：false
示例 4：
輸入：[5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那裡，我們按順序收取 2 張 5 美元的鈔票。
對於接下來的 2 位顧客，我們收取一張 10 美元的鈔票，然後返還 5 美元。
對於最後一位顧客，我們無法退回 15 美元，因為我們現在只有兩張 10 美元的鈔票。
由於不是每位顧客都得到了正確的找零，所以答案是 false。
給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
你可以認為每種硬幣的數量是無限的。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
示例 4：
輸入：coins = [1], amount = 1
輸出：1
示例 5：
輸入：coins = [1], amount = 2
輸出：2
3. 動態規劃與貪心演算法
很奇怪，動態規劃和貪心演算法也有很多相似之處：
相同點：
0，兩者都用於求解最優化問題
1，兩者都將待求解的問題分解成若乾子問題
2，兩者都需要確定最優子結構，才能決定是否可以使用該方法
3，兩者都需要構造遞歸式
最優子結構：一個問題的最優解包含其子問題的最優解
不同點：
1，動態規劃是自底向上計算，類似於將問題的規模從1開始，計算到n,其中i的求解依賴於i-1的結果；貪心演算法則是自頂向下計算，選擇當前一個最優解，然後再看剩餘問題的最優解，一路剝削下去
2，動態規劃比貪心演算法更加細致精確，貪心演算法有時候求不出最優解
貪心演算法：面對規模為n的問題，每次選擇當前情況的一個最優解，然後在看剩餘的n-1規模的問題。
貪心原則：最能符合問題需求的選擇
貪心演算法需要論證
每次貪心選擇的解組合在一起就是最優解 這個結論是否正確
4. Pascal貪心演算法，求解答！
這道題用貪心不大好吧
記得老師以前說過
這種題用DP
這道題是最簡單的01背包
我給你發個資料
那個，發不了啊，上傳失敗
你給我qq吧
P01: 01背包問題
題目
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
注意f[i][v]有意義當且僅當存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢後，最終的答案並不一定是f[N] [V]，而是f[N][0..V]的最大值。如果將狀態的定義中的「恰」字去掉，在轉移方程中就要再加入一項f[i][v-1]，這樣就可以保證f[N] [V]就是最後的答案。至於為什麼這樣就可以，由你自己來體會了。
優化空間復雜度
以上方法的時間和空間復雜度均為O(N*V)，其中時間復雜度基本已經不能再優化了，但空間復雜度卻可以優化到O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組f [0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態f[i -1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。
總結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間復雜度。
P02: 完全背包問題
題目
有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本思路
這個問題非常類似於01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的策略已並非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程，像這樣：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}。這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態的時間則不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度是超過O(VN)的。
將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個復雜度。
一個簡單有效的優化
完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]<=c[j]且w[i]>=w[j]，則將物品j去掉，不用考慮。這個優化的正確性顯然：任何情況下都可將價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對於隨機生成的數據，這個方法往往會大大減少物品的件數，從而加快速度。然而這個並不能改善最壞情況的復雜度，因為有可能特別設計的數據可以一件物品也去不掉。
轉化為01背包問題求解
既然01背包問題是最基本的背包問題，那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是，考慮到第i種物品最多選V/c [i]件，於是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間復雜度，但這畢竟給了我們將完全背包問題轉化為01背包問題的思路：將一種物品拆成多件物品。
更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若干件物品，其中k滿足c[i]*2^k<V。這是二進制的思想，因為不管最優策略選幾件第i種物品，總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/c[i]))件物品，是一個很大的改進。 但我們有更優的O(VN)的演算法。 * O(VN)的演算法 這個演算法使用一維數組，先看偽代碼： <pre class"example"> for i=1..N for v=0..Vf[v]=max{f[v],f[v-c[i]]+w[i]};
你會發現，這個偽代碼與P01的偽代碼只有v的循環次序不同而已。為什麼這樣一改就可行呢？首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮「選入第i件物品」這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮「加選一件第i種物品」這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以並且必須採用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。
這個演算法也可以以另外的思路得出。例如，基本思路中的狀態轉移方程可以等價地變形成這種形式：f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}，將這個方程用一維數組實現，便得到了上面的偽代碼。
總結
完全背包問題也是一個相當基礎的背包問題，它有兩個狀態轉移方程，分別在「基本思路」以及「O(VN)的演算法「的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會，不僅記住，也要弄明白它們是怎麼得出來的，最好能夠自己想一種得到這些方程的方法。事實上，對每一道動態規劃題目都思考其方程的意義以及如何得來，是加深對動態規劃的理解、提高動態規劃功力的好方法。
P03: 多重背包問題
題目
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
基本演算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對於第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}。復雜度是O(V*∑n[i])。
轉化為01背包問題
另一種好想好寫的基本方法是轉化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數為∑n[i]的01背包問題，直接求解，復雜度仍然是O(V*∑n[i])。
但是我們期望將它轉化為01背包問題之後能夠像完全背包一樣降低復雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價於取若干件代換以後的物品。另外，取超過n[i]件的策略必不能出現。
方法是：將第i種物品分成若干件物品，其中每件物品有一個系數，這件物品的費用和價值均是原來的費用和價值乘以這個系數。使這些系數分別為 1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數。例如，如果n[i]為13，就將這種物品分成系數分別為1,2,4,6的四件物品。
分成的這幾件物品的系數和為n[i]，表明不可能取多於n[i]件的第i種物品。另外這種方法也能保證對於0..n[i]間的每一個整數，均可以用若干個系數的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，並不難，希望你自己思考嘗試一下。
這樣就將第i種物品分成了O(log n[i])種物品，將原問題轉化為了復雜度為O(V*∑logn[i])的01背包問題，是很大的改進。
O(VN)的演算法
多重背包問題同樣有O(VN)的演算法。這個演算法基於基本演算法的狀態轉移方程，但應用單調隊列的方法使每個狀態的值可以以均攤O(1)的時間求解。由於用單調隊列優化的DP已超出了NOIP的范圍，故本文不再展開講解。我最初了解到這個方法是在樓天成的「男人八題」幻燈片上。
小結
這里我們看到了將一個演算法的復雜度由O(V*∑n[i])改進到O(V*∑log n[i])的過程，還知道了存在應用超出NOIP范圍的知識的O(VN)演算法。希望你特別注意「拆分物品」的思想和方法，自己證明一下它的正確性，並用盡量簡潔的程序來實現。
P04: 混合三種背包問題
問題
如果將P01、P02、P03混合起來。也就是說，有的物品只可以取一次（01背包），有的物品可以取無限次（完全背包），有的物品可以取的次數有一個上限（多重背包）。應該怎麼求解呢？
01背包與完全背包的混合
考慮到在P01和P02中最後給出的偽代碼只有一處不同，故如果只有兩類物品：一類物品只能取一次，另一類物品可以取無限次，那麼只需在對每個物品應用轉移方程時，根據物品的類別選用順序或逆序的循環即可，復雜度是O(VN)。偽代碼如下：
for i=1..N
if 第i件物品是01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品是完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};
再加上多重背包
如果再加上有的物品最多可以取有限次，那麼原則上也可以給出O(VN)的解法：遇到多重背包類型的物品用單調隊列解即可。但如果不考慮超過NOIP范圍的演算法的話，用P03中將每個這類物品分成O(log n[i])個01背包的物品的方法也已經很優了。
小結
有人說，困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論，但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什麼難題，但將它們簡單地組合起來以後就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎扎實，領會三種基本背包問題的思想，就可以做到把困難的題目拆分成簡單的題目來解決。
P05: 二維費用的背包問題
問題
二維費用的背包問題是指：對於每件物品，具有兩種不同的費用；選擇這件物品必須同時付出這兩種代價；對於每種代價都有一個可付出的最大值（背包容量）。問怎樣選擇物品可以得到最大的價值。設這兩種代價分別為代價1和代價2，第i件物品所需的兩種代價分別為a[i]和b[i]。兩種代價可付出的最大值（兩種背包容量）分別為V和U。物品的價值為w[i]。
演算法
費用加了一維，只需狀態也加一維即可。設f[i][v][u]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態轉移方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法，可以只使用二維的數組：當每件物品只可以取一次時變數v和u採用順序的循環，當物品有如完全背包問題時採用逆序的循環。當物品有如多重背包問題時拆分物品。
物品總個數的限制
有時，「二維費用」的條件是以這樣一種隱含的方式給出的：最多隻能取M件物品。這事實上相當於每件物品多了一種「件數」的費用，每個物品的件數費用均為1，可以付出的最大件數費用為M。換句話說，設f[v][m]表示付出費用v、最多選m件時可得到的最大價值，則根據物品的類型（01、完全、多重）用不同的方法循環更新，最後在f[0..V][0..M]范圍內尋找答案。
另外，如果要求「恰取M件物品」，則在f[0..V][M]范圍內尋找答案。
小結
事實上，當發現由熟悉的動態規劃題目變形得來的題目時，在原來的狀態中加一緯以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。
P06: 分組的背包問題
問題
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
演算法
這個問題變成了每組物品有若干種策略：是選擇本組的某一件，還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值，則有f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品i屬於第k組}。
使用一維數組的偽代碼如下：
for 所有的組k
for 所有的i屬於組k
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]}
另外，顯然可以對每組中的物品應用P02中「一個簡單有效的優化」。
小結
分組的背包問題將彼此互斥的若干物品稱為一個組，這建立了一個很好的模型。不少背包問題的變形都可以轉化為分組的背包問題（例如P07），由分組的背包問題進一步可定義「泛化物品」的概念，十分有利於解題。
P07: 有依賴的背包問題
簡化的問題
這種背包問題的物品間存在某種「依賴」的關系。也就是說，i依賴於j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設沒有某個物品既依賴於別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。
演算法
這個問題由NOIP2006金明的預算方案一題擴展而來。遵從該題的提法，將不依賴於別的物品的物品稱為「主件」，依賴於某主件的物品稱為「附件」。由這個問題的簡化條件可知所有的物品由若干主件和依賴於每個主件的一個附件集合組成。
按照背包問題的一般思路，僅考慮一個主件和它的附件集合。可是，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件後再選擇一個附件，選擇主件後再選擇兩個附件……無法用狀態轉移方程來表示如此多的策略。（事實上，設有n個附件，則策略有2^n+1個，為指數級。）
考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應於P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應於這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉化並不能給出一個好的演算法，因為物品組中的物品還是像原問題的策略一樣多。
再考慮P06中的一句話： 可以對每組中的物品應用P02中「一個簡單有效的優化」。這提示我們，對於一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結果。所以，我們可以對主件i的「附件集合」先進行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應的最大價值f'[0..V-c[i]]。那麼這個主件及它的附件集合相當於V-c[i]+1個物品的物品組，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數級的策略中有很多策略都是冗餘的，通過一次01背包後，將主件i轉化為 V-c[i]+1個物品的物品組，就可以直接應用P06的演算法解決問題了。
更一般的問題
更一般的問題是：依賴關系以圖論中「森林」的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多隻依賴於一個物品（只有一個主件）且不出現循環依賴。
解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是，由於附件可能還有附件，就不能將每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合，則它必定要被先轉化為物品組，然後用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。
事實上，這是一種樹形DP，其特點是每個父節點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了「泛化物品」的思想。看完P08後，你會發現這個「依賴關系樹」每一個子樹都等價於一件泛化物品，求某節點為根的子樹對應的泛化物品相當於求其所有兒子的對應的泛化物品之和。
小結
NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。後來我通過思考發現通過引入「物品組」和「依賴」的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關系：物品不能既作主件又作附件，每個主件最多有兩個附件，可以發現一個主件和它的兩個附件等價於一個由四個物品組成的物品組，這便揭示了問題的某種本質。
我想說：失敗不是什麼丟人的事情，從失敗中全無收獲才是。
P08: 泛化物品
定義
考慮這樣一種物品，它並沒有固定的費用和價值，而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。
更嚴格的定義之。在背包容量為V的背包問題中，泛化物品是一個定義域為0..V中的整數的函數h，當分配給它的費用為v時，能得到的價值就是h(v)。
這個定義有一點點抽象，另一種理解是一個泛化物品就是一個數組h[0..V]，給它費用v，可得到價值h[V]。
一個費用為c價值為w的物品，如果它是01背包中的物品，那麼把它看成泛化物品，它就是除了h(c)=w其它函數值都為0的一個函數。如果它是完全背包中的物品，那麼它可以看成這樣一個函數，僅當v被c整除時有h(v)=v/c*w，其它函數值均為0。如果它是多重背包中重復次數最多為n的物品，那麼它對應的泛化物品的函數有h(v)=v/c*w僅當v被c整除且v/c<=n，其它情況函數值均為0。
一個物品組可以看作一個泛化物品h。對於一個0..V中的v，若物品組中不存在費用為v的的物品，則h(v)=0，否則h(v)為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價於一個物品組，自然也可看作一個泛化物品。
泛化物品的和
如果面對兩個泛化物品h和l，要用給定的費用從這兩個泛化物品中得到最大的價值，怎麼求呢？事實上，對於一個給定的費用v，只需枚舉將這個費用如何分配給兩個泛化物品就可以了。同樣的，對於0..V的每一個整數v，可以求得費用v分配到h和l中的最大價值f(v)。也即f(v)=max{h(k)+l(v-k)|0<=k<=v}。可以看到，f也是一個由泛化物品h和l決定的定義域為0..V的函數，也就是說，f是一個由泛化物品h和 l決定的泛化物品。
由此可以定義泛化物品的和：h、l都是泛化物品，若泛化物品f滿足f(v)=max{h(k)+l(v-k)|0<=k<=v}，則稱f是h與l的和，即f=h+l。這個運算的時間復雜度是O(V^2)。
泛化物品的定義表明：在一個背包問題中，若將兩個泛化物品代以它們的和，不影響問題的答案。事實上，對於其中的物品都是泛化物品的背包問題，求它的答案的過程也就是求所有這些泛化物品之和的過程。設此和為s，則答案就是s[0..V]中的最大值。
背包問題的泛化物品
一個背包問題中，可能會給出很多條件，包括每種物品的費用、價值等屬性，物品之間的分組、依賴等關系等。但肯定能將問題對應於某個泛化物品。也就是說，給定了所有條件以後，就可以對每個非負整數v求得：若背包容量為v，將物品裝入背包可得到的最大價值是多少，這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數的函數——包含了關於問題本身的高度濃縮的信息。一般而言，求得這個泛化物品的一個子域（例如0..V）的值之後，就可以根據這個函數的取值得到背包問題的最終答案。
綜上所述，一般而言，求解背包問題，即求解這個問題所對應的一個函數，即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物品的和然後求之。
小結
本講可以說都是我自己的原創思想。具體來說，是我在學習函數式編程的 Scheme 語言時，用函數編程的眼光審視各類背包問題得出的理論。這一講真的很抽象，也許在「模型的抽象程度」這一方面已經超出了NOIP的要求，所以暫且看不懂也沒關系。相信隨著你的OI之路逐漸延伸，有一天你會理解的。
我想說：「思考」是一個OIer最重要的品質。簡單的問題，深入思考以後，也能發現更多。
P09: 背包問題問法的變化
以上涉及的各種背包問題都是要求在背包容量（費用）的限制下求可以取到的最大價值，但背包問題還有很多種靈活的問法，在這里值得提一下。但是我認為，只要深入理解了求背包問題最大價值的方法，即使問法變化了，也是不難想出演算法的。
例如，求解最多可以放多少件物品或者最多可以裝滿多少背包的空間。這都可以根據具體問題利用前面的方程求出所有狀態的值（f數組）之後得到。
還有，如果要求的是「總價值最小」「總件數最小」，只需簡單的將上面的狀態轉移方程中的max改成min即可。
5. 是不是所有的貪心題理論上都可以用動態規劃做
貪心演算法：
所作出的每一步貪心決策都是無法改變的，下一步的最優解是由上一步的最優解直接推導出來的；
也就是說，上一步的最優解就是組成下一步最優解的一部分，所以貪心演算法是不會保留上一步之前得出的解的
動態規劃演算法：
全局的最優解是包含某個局部最優解的，但這個局部最優解不一定就是上一步的最優解，所以動態規劃演算法是需要保留所有之前所得出的最優解的；
也就是說，已經得到的所有最優解中，包含了推導出下一步最優解的信息，不同於貪心的是我們並不確定到底是那一個，所以計算過程中是需要保留所有得出的子最優解的
都是通過求解子最優解來得出全劇最優解的演算法，但可以看出貪心演算法的適用范圍更小，動態規劃的適用范圍更大，所以理論上，動態規劃演算法是可以解決貪心演算法能解決的問題的
6. 貪心演算法——活動安排問題
•貪心演算法的特點是每個階段所作的選擇都是局部最優的，它期望通過所作的局部最優選擇產生出一個全局最優解。
貪心與動態規劃： 與動態規劃不同的是，貪心是 鼠目寸光 ；動態規劃是 統攬全局 。
–動態規劃：每個階段產生的都是全局最優解
•第i階段的「全局」： 問題空間為(a1, … , ai)
•第i階段的「全局最優解」：問題空間為 (a1, … , ai)時的最優解
–貪心：每個階段產生的都是局部最優解
•第i階段的「局部」：問題空間為按照貪心策略中的優先順序排好序的第i個輸入ai
•第i階段的「局部最優解」： ai
•貪心選擇性質：所求問題的全局最優解可以通過一系列局部最優的選擇（即貪心選擇）來達到。
–這是貪心演算法與動態規劃演算法的主要區別。
•最優子結構性質：當原問題的最優解包含子問題的最優解時，稱此問題具有最優子結構性質。
最優子結構性質是該問題可用動態規劃演算法或貪心演算法求解的關鍵特徵
•要求高效地安排一系列爭用某一公共資源（例如會議室）的活動（使盡可能多的活動能兼容使用公共資源）。
–設有n個活動的集合E={e1,e2…en}，其中每個活動都要求使用同一資源，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si<fi。如果選擇了活動i，則它在半開時間區間[si,fi)內佔用資源。
–若區間[si,fi)與區間[sj,fj)不相交，則稱ei和ej是相容的。也就是說，當si≥fj或sj≥fi時，活動i和活動j相容。
•活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。
7. (三) 貪心演算法
貪心演算法的思想非常簡單且演算法效率很高，在一些問題的解決上有著明顯的優勢。
假設有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就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。
8. 活動選擇（貪心演算法）
參考： 【演算法導論】貪心演算法之活動選擇問題
貪心演算法（Greedy Algorithm）在每一步都做出當時看起來最佳的選擇，寄希望這樣的選擇能導致全局最優解。
這種演算法並不能保證得到最優解，但對很多問題確實可以求得最優解。
假定有一個n個活動的集合S={a1,a2,a3,...,an},這些活動 使用同一個資源 ，而這個資源在某個時刻 只能給一個活動使用 。每個活動都有一個 開始時間si 和一個 結束時間fi ，其中0<=si<fi<=∞。
如果活動ai被選中，則此活動發生在 半開區間[si,fi) 中。
若兩個活動ai和aj的 時間區間不重疊 ，則稱這兩個活動是 兼容 的
在活動選擇問題中，我們希望選出一個最大兼容活動集。
假定活動已經按照 結束時間遞增順序 排好序
f1<=f2<=f3<=...<=fn
考慮如下例子：
可以看到，{a3,a9,a11}是由相互兼容的活動組成。但它不是一個最大集，{a1,a4,a8,a11}更大，是一個最大集。（最大集不唯一）
假設：Sij表示在ai結束之後，在aj開始之前的活動的 集合 。Aij表示Sij的一個最大相互兼容的活動子集。
那麼只要Sij非空，則Aij至少會包含一個活動，假設為ak。那麼可以將Aij分解為：Aij = Aik+ak+Akj。
假設Cij為Aij的大小，那麼有Cij=cik+ckj+1。
於是，我們可以利用動態規劃得到這個問題的遞歸解
我們當然可以利用動態規劃自底向上地求解這個問題，但是我們可以利用貪心演算法更快地求解問題答案。
我們選擇活動 結束時間最早 的那個活動，這樣能夠給其他活動盡可能的騰出多餘的時間，而後每一步都在剩下的活動中選取最早的活動，這樣就可以獲得一個最優解。
為什麼貪心選擇——最早結束的活動ai——總是最優解的一部分呢？
假設Aij是Sij的某個最大兼容活動集，假設Aij中，最早結束的活動是an。（an是最優解中最早結束的，不一定是原先活動中最早結束的）我們要證明我們選擇的a1（原先活動集中最早結束的）也在最優解中。
分兩種情況：
①如果an=a1，則得證
②如果an不等於a1，則an的結束時間一定會 晚於 a1的結束時間，我們用a1去 替換 Aij中的an，於是得到A'，由於a1比an結束的早，而Aij中的其他活動都比an的結束時間開始 的要晚，所以A'中的 其他活動 都與a1不相交 ，所以A'中的所有活動是兼容的，所以A`也是Sij的一個最大兼容活動集。
（簡單說，就是用a1 替換 an，得到另一個解A'，由於a1最早結束，當然與其他活動不相交，於是A'也兼容且個數和A一樣，所以A'也是最優解）
於是證明了命題。
通過以上分析，我們可以反復地選擇最先結束的活動，保留於此活動兼容的活動，重復執行，直到不再有剩餘活動。
貪心演算法通常是 自頂向下 地設計：做出一個選擇，然後求解剩下的那個子問題
為了方便初始化，我們添加一個虛擬活動a0，其結束時間為f0=0
由於我們之前就已經將活動按結束時間排好序，每一次找元素都只對元素訪問一次，所以貪心演算法的時間復雜度是大theta（n）