最優解貪心演算法

Ⅰ 貪心演算法得出來的一定是最優解嗎

一般是，但也有不是的情況，要得到最優最好用搜索或動歸

Ⅱ 怎樣應用貪心演算法求得最優解

動態規劃要求。。具有最優子結構，記f[i]最優時，f[i - 1]的解也最優。。。最終可以得到最優解

貪心演算法，一般只能得到近優解或者局部最優解。。

Ⅲ 貪心演算法幾個經典例子

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

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

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

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

Ⅳ 貪心演算法及其應用

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

比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝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]，期望值就是盡可能多的區間。

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

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

Ⅳ 貪心演算法的基本思路

1.建立數學模型來描述問題
⒉把求解的問題分成若干個子問題。
⒊對每一子問題求解，得到子問題的局部最優解。
⒋把子問題的解局部最優解合成原來解問題的一個解。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步
do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解。
下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。

Ⅵ 貪心演算法的本質

1. 貪心法（Greedy Algorithm）定義

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

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

2. 對貪心法的深入理解

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

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

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

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

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

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

（4）一般步驟：

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

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

③證明做出貪心選擇後：

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

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

並完成2°

3. 貪心法與動態規劃

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

Ⅶ 貪心演算法的基本思想

貪心演算法的基本思想就是分級處理。

貪心演算法是一種分級處理的方法。用貪心法設計演算法的特點是一步一步的進行，根據某個優化測度（可能是目標函數，也可能不是目標函數），每一步上都要保證能獲得局部最優解。每一步只考慮一個數據，它的選取應滿足局部優化條件。若下一個數據與部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加為止。

3、還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。

4、選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。

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

Ⅹ 將最優裝載問題的貪心演算法推廣到2艘船的情形，貪心演算法仍能產生最優解嗎

貪心演算法不能產生最優解。

兩艘船的裝載問題，是先裝完第一艘，再裝第二艘，所以就必須把第一艘盡可能的裝滿，才能使總的裝載量更多。

對於一個具體問題，要確定它是否具有貪心選擇的性質，必須證明每一步所作的貪心選擇最終能得到問題的最優解，通常可以首先證明問題的一個整體最優解，是從貪心選擇開始的，而且作了貪心選擇後，原問題簡化為一個規模更小的類似子問題。

(10)最優解貪心演算法擴展閱讀：

兩艘船的裝載問題需要用的是回溯法，有了問題的解空間後，還需要將解空間有效地組織起來，使得回溯法能方便地搜索整個解空間，通常將解空間組織成樹或圖的形式。

如果在當前的擴展結點處不能再向縱深方向移動，則當前的擴展結點就成為死結點。此時應往回移動(回溯)至最近的一個活結點處，並使其成為當前的擴展結點。回溯法以上述工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結點時為止。

此外，貪心演算法的每一次操作都對結果產生直接影響，而動態規劃則不是。貪心演算法對每個子問題的解決方案都做出選擇，不能回退；動態規劃則會根據以前的選擇結果對當前進行選擇，有回退功能。