演算法貪心法

1. 程序員都應該精通的六種演算法，你會了嗎

對於一名優秀的程序員來說，面對一個項目的需求的時候，一定會在腦海里浮現出最適合解決這個問題的方法是什麼，選對了演算法，就會起到事半功倍的效果，反之，則可能會使程序運行效率低下，還容易出bug。因此，熟悉掌握常用的演算法，是對於一個優秀程序員最基本的要求。

那麼，常用的演算法都有哪些呢？一般來講，在我們日常工作中涉及到的演算法，通常分為以下幾個類型：分治、貪心、迭代、枚舉、回溯、動態規劃。下面我們來一一介紹這幾種演算法。

一、分治演算法

分治演算法，顧名思義，是將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

分治演算法一般分為三個部分：分解問題、解決問題、合並解。

分治演算法適用於那些問題的規模縮小到一定程度就可以解決、並且各子問題之間相互獨立，求出來的解可以合並為該問題的解的情況。

典型例子比如求解一個無序數組中的最大值，即可以採用分治演算法，示例如下：

def pidAndConquer(arr,leftIndex,rightIndex):

if(rightIndex==leftIndex+1 || rightIndex==leftIndex){

return Math.max(arr[leftIndex],arr[rightIndex]);

}

int mid=(leftIndex+rightIndex)/2;

int leftMax=pidAndConquer(arr,leftIndex,mid);

int rightMax=pidAndConquer(arr,mid,rightIndex);

return Math.max(leftMax,rightMax);

二、貪心演算法

貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

貪心演算法的基本思路是把問題分成若干個子問題，然後對每個子問題求解，得到子問題的局部最優解，最後再把子問題的最優解合並成原問題的一個解。這里要注意一點就是貪心演算法得到的不一定是全局最優解。這一缺陷導致了貪心演算法的適用范圍較少，更大的用途在於平衡演算法效率和最終結果應用，類似於：反正就走這么多步，肯定給你一個值，至於是不是最優的，那我就管不了了。就好像去菜市場買幾樣菜，可以經過反復比價之後再買，或者是看到有賣的不管三七二十一先買了，總之最終結果是菜能買回來，但搞不好多花了幾塊錢。

典型例子比如部分背包問題：有n個物體，第i個物體的重量為Wi，價值為Vi，在總重量不超過C的情況下讓總價值盡量高。每一個物體可以只取走一部分，價值和重量按比例計算。

貪心策略就是，每次都先拿性價比高的，判斷不超過C。

三、迭代演算法

迭代法也稱輾轉法，是一種不斷用變數的舊值遞推新值的過程。迭代演算法是用計算機解決問題的一種基本方法，它利用計算機運算速度快、適合做重復性操作的特點，讓計算機對一組指令(或一定步驟)進行重復執行，在每次執行這組指令(或這些步驟)時，都從變數的原值推出它的一個新值。最終得到問題的結果。

迭代演算法適用於那些每步輸入參數變數一定，前值可以作為下一步輸入參數的問題。

典型例子比如說，用迭代演算法計算斐波那契數列。

四、枚舉演算法

枚舉演算法是我們在日常中使用到的最多的一個演算法，它的核心思想就是:枚舉所有的可能。枚舉法的本質就是從所有候選答案中去搜索正確地解。

枚舉演算法適用於候選答案數量一定的情況。

典型例子包括雞錢問題，有公雞5，母雞3，三小雞1，求m錢n雞的所有可能解。可以採用一個三重循環將所有情況枚舉出來。代碼如下：

五、回溯演算法

回溯演算法是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。

許多復雜的，規模較大的問題都可以使用回溯法，有「通用解題方法」的美稱。

典型例子是8皇後演算法。在8 8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問一共有多少種擺法。

回溯法是求解皇後問題最經典的方法。演算法的思想在於如果一個皇後選定了位置，那麼下一個皇後的位置便被限制住了，下一個皇後需要一直找直到找到安全位置，如果沒有找到，那麼便要回溯到上一個皇後，那麼上一個皇後的位置就要改變，這樣一直遞歸直到所有的情況都被舉出。

六、動態規劃演算法

動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。

動態規劃演算法適用於當某階段狀態給定以後，在這階段以後的過程的發展不受這段以前各段狀態的影響，即無後效性的問題。

典型例子比如說背包問題，給定背包容量及物品重量和價值，要求背包裝的物品價值最大。

2. 簡述貪心，遞歸，動態規劃，及分治演算法之間的區別和聯系

聯系：都是問題求解之時的一種演算法。

區別：

一、作用不同

1、貪心演算法：把子問題的解局部最優解合成原來解問題的一個解。

2、遞歸演算法：問題解法按遞歸演算法實現。如Hanoi問題；數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。

3、動態規劃：動態規劃演算法通常用於求解具有某種最優性質的問題。

4、分治演算法：可以再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。

二、方法不同

1、貪心演算法：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，演算法得到的是在某種意義上的局部最優解。

2、遞歸演算法：通過重復將問題分解為同類的子問題而解決問題。

3、動態規劃：將過程分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個過程達到最好的活動效果。

4、分治演算法：將一個規模為N的問題分解為K個規模較小的子問題。

三、特點不同

1、貪心演算法：根據題意選取一種量度標准。

2、遞歸演算法：遞歸就是在過程或函數里調用自身。

3、動態規劃：雖然動態規劃主要用於求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。

4、分治演算法：原問題可以分解為多個子問題；原問題在分解過程中，遞歸地求解子問題；在求解並得到各個子問題的解後。

3. 貪心演算法的本質

1. 貪心法（Greedy Algorithm）定義

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

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

2. 對貪心法的深入理解

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

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

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

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

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

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

（4）一般步驟：

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

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

③證明做出貪心選擇後：

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

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

並完成2°

3. 貪心法與動態規劃

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

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

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

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

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