貪心最優存儲演算法推廣

㈠ 貪心思想

在學習數據結構的時候，我們已經見過了貪心思想在Prim和Kruskal中的完美應用，貪心思想因為其的簡潔在演算法中經常會被用到，有的時候在生活中，我們也會無意中使用到l貪心演算法。比如在去shopping時，經常需要進行找零錢的過程，我們總是不自覺的先把大的找出來。

那麼什麼是貪心思想？

貪心演算法總是作出在當前看來最好的選擇，也就是說貪心演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

只有在滿足最優子結構的情況下貪心演算法得到的結果才是最優結果。

比如找錢的問題，我要給你一百，那麼我盡可能每一次給你最多的。

或者比如磁碟的最優存儲問題，所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。

Prim和kruskal演算法都是每次選擇最小的邊納入生成樹。

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這也是貪心問題和動態規劃問題的主要區別。

在n行m列的正整數矩陣中，要求從每一行中選一個數，使得選出的n個數的和最大。

可運用貪心策略，選n次，每一次選相應行中的最大值即可。

但是，在一個n*m的方格陣中，每一格子賦予一個數，規定每次移動時只能向上或向右，現試找出一條路徑，使其從左下角至右上角所經過的權值之和最大。

同樣考慮貪心策略，從左下角向右上角移動，每次移動選擇權值較大的一個方向。

以2*3矩陣為例，採用貪心的策略得到的是1,3,4,6和為14但是實際的最優結果為1,2,100,6和為109.

所以說貪心演算法並不是總是可行，證明當前問題存在貪心選擇性質（全局最優解可以通過局部最優貪心選擇達到）和最優子結構性質（問題的最優解包含了其子問題的最優解）。所以貪心問題如果當前的選擇不會干擾之後的選擇，則不會出現問題。

其他的情況就需要進行證明，證明的最好辦法就是將最小子問題進行一步步的合並，直到最後還原為最後的原問題，若所得到的解是總體最優的則可以使用貪心思想，否則不可以。

比如上面的問題，我們的走一步的最優解為1，3，然後我們判斷一次走兩步的最優解是否任然為1,3這個路徑，答案顯然不是，變為 1,2,100這個路徑，所以顯然不能使用貪心思想。

假設1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張。現在要用這些錢來支付K元，至少要用多少張紙幣？用貪心演算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。

有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。

部分背包問題， 有n個物體，第i個物體重量為wi,價值為vi,在總重量不超過C的情況下，讓總價值盡可能的高。每個物體都可以只取一部分。

我們可以考慮重量和價值的比值作為單價。

㈡ 如何用貪心演算法解決磁碟文件最優存儲問題

dp??
方程為
a(fi,fj)=min{(a(fi,fk)+a(fk,fj)),a(fi,fj)}(k=i+1,i+2...j-1);

㈢ 演算法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

㈣ 貪心演算法總結

做了這10道題，其實發現貪心演算法沒有什麼規律，要說有什麼共同特點就是都是由局部最優從而推出全局最優，每個題基本上都要考慮其局部最優是什麼，其全局最優是什麼，所以雖然都用到了貪心演算法的思想，但是題與題之間又沒有什麼規律可言。

現在把這10道題的思路總結一下（總結主要以我的主觀看法在寫，可能別人看會不知道我在說什麼）

1.分發餅干：

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路：想要完成最多的小孩滿足，那麼就得最小的餅干給胃口最小的小孩

這里的貪心思想，

局部最優就是盡可能讓一個餅干喂飽一個

全局最優就是最多的小孩滿足

2.擺動序列：

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

思路：這里要找到最長的擺動序列，那麼其實就是找那些波峰波谷，如圖所示

可以看出來，在到達波峰波谷的路上有幾個數字不會影響什麼，可以直接去掉。

那麼這里的局部最優就是把單調坡上的點刪掉，保留最多的波峰波谷

全局最優就是得到對多的波峰波谷，即最長的擺動序列

3.最大子序和

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

這道題顯然可以暴力解出來，即列出所有子序和，找出最大的，不過計算量會比貪心大很多。

這里主要介紹貪心解的思想：

想要得到最大子序和，就得保證每次相加時，相加後不能為負數，因為負數繼續往下加一定是拉低總和的，那麼我們當加成到負數時就重新從下個數開始加，並實時記錄最大的子序和，這樣一遍循環就能得出最大子序和。

局部最優：加成負數就立刻停止，並從下個元素重新開始

全局最優：得到最大子序和

4.買賣股票的最佳時機II

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html

思路：想要得到最大利潤，那就要低價買入高價賣出，那麼怎樣的買賣才能得到最大利潤呢。

這里就體現出貪心演算法的「貪」字（我猜的），這道題貪在哪呢，貪在只要有利可圖就去做，即只要今天買入的價錢比明天賣出的價錢底，即有利可圖，那麼我就去做，做就是在今天買入，在明天賣出。

局部最優：得到每天的最大正利潤

全局最優：得到最大利潤

5.跳躍游戲

https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

思路：每個數組的元素代表的是可以跳的最遠下標，那麼我們只要使那個最遠下標包含最後一個下標就是可以跳到，那麼我們每跳到一個位置就要更新那個可以跳的范圍，即可以跳到的最遠下標。

局部最優：每次跳躍都得出最遠的跳躍范圍

全局最優：最後能跳到的最大范圍

6.跳躍游戲II

https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

思路：這道題要得到最小的跳躍數，其實只要保證跳的是位置是可以跳范圍內更新最遠范圍的位置就可以了。

為什麼這么說呢？以題例來說：

我們剛開始在『0』的位置，我們能跳到『1』和『2』的位置，那麼我們怎麼跳呢？可以看到跳到『1』之後更新的最大范圍是『4』，跳到『2』之後更新的最大范圍是『3』，所以我們就跳『2』了，因為跳『1』之後更新的最大可跳范圍更大包含了跳『2』的最大可跳范圍，那麼肯定是跳『3』最優呀，這里就體現了局部最優的思想。

局部最優：每次跳後，更新的最大可調范圍最大

全局最優：跳躍次數最少

7.K次取反後最大化的數組和

https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

思路：想要得到最大數組和，我們就可以想到怎樣做呢？

一，盡可能保證負數最少

二，負數絕對值大的優先變正

三，正數絕對值小的優先變負，有零變零

本著這三條原則做，就能做出來。

那麼這道題體現了什麼貪心思想呢？

我感覺，前面那三條都是貪心中『貪』的體現

在負數中，局部最優就是：絕對值大的負數優先變正

在正數中，局部最優就是：絕對值小的正數變負，有零變零

得到的全局最優：數組和最大

8.加油站

https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

思路：首先可以想到這道題是可以暴力解出來了，即分別以每個加油站為起點，得出可以跑一圈的加油站

那麼貪心思想做，該怎麼做呢，首先可以想到，如果以一個1點為起點當跑著跑著跑到3，油變為負數時，那麼說明以這個起點是不行的，但是以2或3為起點行不行呢？答案肯定是不行的，因為1跑到3，油變為負，說明1~3的gas=0的，所以可以得出，如果1~3油數變為負數，那麼由2~3油數肯定也為負數。

所以這里就可以得出，如果經過幾個加油站油數變為負了，那麼起點就更新為這一段路的下個加油站跑

局部最優：油量一旦為負，就從下個加油站重新跑

全局最優：得出可以跑一圈的加油站起點

9.分發糖果

https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

思路：每個孩子至少一個，如果一個孩子比他旁邊的孩子優秀，就要比他旁邊的糖果多，這道題一旦兩邊都考慮很容易顧此失彼，所以我們就定義兩個循環，分別從左到右，從右到左去考慮，只要更優秀則比他旁邊的多1，如果已經多了就不用變了。

局部最優：保證優秀的孩子比他旁邊的孩子糖果多

全局最優：滿足題中條件，至少要發的糖果

10.檸檬水找零

https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

思路：我們在找零時要遵守的規則一定是：

5 得5

10 得10減5

15 得15，優先減一個10減一個5  如果10塊沒有則減三個5

局部最優：以最少用的5塊的方式找零

全局最優：得到找零能否進行下去

㈤ [演算法] 貪心演算法證明思路

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

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

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

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

㈥ (三) 貪心演算法

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

假設有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就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。

㈦ 回溯演算法與貪心演算法

回溯是遞歸的副產品，只要有遞歸就會有回溯 ，所以回溯法也經常和二叉樹遍歷，深度優先搜索混在一起，因為這兩種方式都是用了遞歸。

回溯法就是暴力搜索，並不是什麼高效的演算法，最多再剪枝一下。

回溯演算法能解決如下問題：

組合問題：N個數裡面按一定規則找出k個數的集合

排列問題：N個數按一定規則全排列，有幾種排列方式

切割問題：一個字元串按一定規則有幾種切割方式

子集問題：一個N個數的集合里有多少符合條件的子集

棋盤問題：N皇後，解數獨等等

回溯演算法的本質是縱向遍歷

回溯演算法模板為

貪心的本質是選擇每一階段的局部最優，從而達到全局最優

貪心演算法一般分為如下四步：

將問題分解為若干個子問題

找出適合的貪心策略

求解每一個子問題的最優解

將局部最優解堆疊成全局最優解

eg：擺動序列

如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為擺動序列。第一個差（如果存在的話）可能是正數或負數。少於兩個元素的序列也是擺動序列。

例如， [1,7,4,9,2,5] 是一個擺動序列，因為差值 (6,-3,5,-7,3) 是正負交替出現的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最後一個差值為零。

給定一個整數序列，返回作為擺動序列的最長子序列的長度。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序。

示例 2:

輸入: [1,17,5,10,13,15,10,5,16,8]

輸出: 7

解釋: 這個序列包含幾個長度為 7 擺動序列，其中一個可為[1,17,10,13,10,16,8]。

㈧ 貪心演算法總結 Greedy Algorithms

反證法：
假設貪心不是最優解：

先考慮如何排序

Exchange argument:通過交換元素將最優解轉換為貪心解，但還保持最優性

當cache中不存在所需元素時，需要訪問cache交換元素。
目標：cache misses的次數最少

最優演算法：cache miss時替換當前future queries中最遠訪問的元素。
e.g. future queries中第一個元素g出現cache miss, 需要exchange，判斷current cache中需要替換哪個元素。
在future queries中

思路：構造最優規劃 ，它有最小的cache misses次數；Farthest-In-Future規劃 ,兩者在前 個請求的序列是相同的，如果能證明在第 步時， 可以轉化為 並且沒有增加cache misses的次數，則可以說明 是最優解。
最開始，假設 和 中元素如下：

Case 1: 元素已經在Cache中
假設下一個請求的元素是d顯然兩者都不會發生cache miss，故兩者總的cache misses次數還是相同；

Case 2: 元素不在Cache中， 和 與外界交換相同的元素
假設下一個請求的元素是e,兩者都用a與其交換，有

和 都增加了一次cache misses，故總cache misses次數還是相同；
Case 3: 元素不在Cache中， 和 與外界交換不同的元素
假設下一個請求的元素是e, 交換a, 交換b,有

之後，下一個請求的元素有四種情況：
Case 3a: 元素在 中, 不在 中; S交換a
也就是請求b,這時S用a交換b,有

有兩次cache misses，而 只有一次，之後 和 序列又保持一致；
Case 3b: 元素在 中, 不在 中; S不交換a
也就是請求b，S用c交換b，有

用a交換c，有

兩者cache misses次數相同，之後 和 序列又保持一致
Case 3c: 元素在 中, 不在 中
即請求a，這種情況不可能發生，因為S_{FF}移出的是最遠需要的元素，即request中a會排在b之後；
Case 3d: 元素不在 和 中
假設請求f, 用a交換f, 用b交換f,有

兩者cache misses次數相同，之後 和 序列又保持一致
的cache misses次數不會多於最優解 , 即 是最優解。

Single-link k-clustering 演算法：

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

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

值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。比如， 求最小生成樹的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，則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候,優先裝重量小的,這樣的問題就可以解決.

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