區間覆蓋貪心演算法

❶ 貪心演算法及其應用

求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。

比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝100KG重量的袋子，怎麼裝才能使得袋子中的豆子價值最大？

我們首先看看這個問題是否符合貪心演算法的使用場景？限制值是袋子100KG，期望值是袋子裡面的價值最高。所以是符合的。那麼我們嘗試著應用下貪心演算法的方法，每一個步驟都尋找當下的最優解，怎麼做呢？

把倉庫裡面的每種豆子價值除以重量，得出每種豆子的單價，那麼當下的最優解，肯定是盡可能最多地裝單價最貴的，也就是先把20KG的黃豆都裝上，然後再把30KG的綠豆都裝上，再裝50KG的紅豆，那麼此時正好裝滿袋子，總價值將是270元，這就是通過貪心演算法求解的答案。

貪心演算法的應用在這個問題上的求解是否是最優解需要一個很復雜的數學論證，我們不用那樣，只要心裡舉幾個例子，驗證下是否比它更好即可，如果舉不出例子，那麼就可以認為這就是最優解了。

雖然貪心演算法雖然在大部分實踐場景中都能得到最優解，但是並不能保證一定是最優解。比如在如下的有向帶權圖中尋找從S到T的最短路徑，那麼答案肯定就是S->A->E->T，總代價為1+4+4=9；

然而，實際上的最短路徑是S->B->D->T，總代價為6。

所以，不能所有這類問題都迷信貪心演算法的求解，但其作為一種演算法指導思想，還是很值得學習的。

除了以上袋子裝豆子的問題之外，還有很多應用場景。這種問題能否使用貪心演算法來解決的關鍵是你能否將問題轉換為貪心演算法適用的問題，即找到問題的限制值和期望值。

我們有m個糖果要分給n個孩子，n大於m，註定有的孩子不能分到糖果。其中，每個糖果的大小都不同，分別為S1,S2,S3...,Sm，每個孩子對糖果的需求也是不同的，為N1,N2,N3...,Nn，那麼我們如何分糖果，才能盡可能滿足最多數量孩子的需求？

這個問題中，限制值是糖果的數量m，期望值滿足最多的孩子需求。對於每個孩子，能用小的糖果滿足其需求，就不要用大的，避免浪費。所以我們可以給所有孩子的需求排個序，從需求最小的孩子開始，用剛好能滿足他的糖果來分給他，以此來分完所有的糖果。

我們有1元、5元、10元、20元、50元、100元紙幣各C1、C5、C10、C20、C50、C100張，現在要購買一個價值K元的東西，請問怎麼才能適用最少的紙幣？

這個問題應該不難，限制值是各個紙幣的張數，期望值是適用最少的紙幣。那麼我們就先用面值最大的100元去付錢，當再加一張100元就超過K時，就更換小面額的，直至正好為K元。

對於n個區間[L1,R1],[L2,R2]...[Ln,Rn]，我們怎麼從中選出盡可能多的區間，使它們不相交？

我們需要把這個問題轉換為符合貪心演算法特點的問題，假設這么多區間的最左端點是Lmin，最右端點是Rmax，那麼問題就是在[Lmin,Rmax]中，選擇盡可能多的區間往裡面塞，並且保證它們不相交。這里，限制值就是區間[Lmin,Rmax]，期望值就是盡可能多的區間。

我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。

貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。

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

❸ 活動選擇（貪心演算法）

參考： 【演算法導論】貪心演算法之活動選擇問題

貪心演算法（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）

❹ 貪心演算法——活動安排問題

•貪心演算法的特點是每個階段所作的選擇都是局部最優的，它期望通過所作的局部最優選擇產生出一個全局最優解。

貪心與動態規劃： 與動態規劃不同的是，貪心是 鼠目寸光 ；動態規劃是 統攬全局 。

–動態規劃：每個階段產生的都是全局最優解

•第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相容。

•活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

❺ 演算法怎麼學

貪心演算法的定義：

貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，只做出在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

解題的一般步驟是：

1.建立數學模型來描述問題；

2.把求解的問題分成若干個子問題；

3.對每一子問題求解，得到子問題的局部最優解；

4.把子問題的局部最優解合成原來問題的一個解。

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

話不多說，我們來看幾個具體的例子慢慢理解它：

1.活動選擇問題

這是《演算法導論》上的例子，也是一個非常經典的問題。有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。

關於貪心演算法的基礎知識就簡要介紹到這里，希望能作為大家繼續深入學習的基礎。

❻ 求一個演算法(貪心演算法)

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

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