❶ 五大常用演算法之一：貪心演算法
所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，換句話說，當考慮做何種選擇的時候，我們只考慮對當前問題最佳的選擇而不考慮子問題的結果。這是貪心演算法可行的第一個基本要素。貪心演算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。 對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。問題的最優子結構性質是該問題可用貪心演算法求解的關鍵特徵。
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。比如， 求最小生成樹的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，則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候,優先裝重量小的,這樣的問題就可以解決.
所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）。
❷ 貪心演算法的證明方法
貪心演算法的基本思路如下：
1.建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
----------------------------------------------
其實歸納起來也就一個類。其他的都是分支
❸ 如何證明貪心演算法
貪心演算法的基本思路如下：
1.建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
❹ 關於編程的貪心法
定義
所謂貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。 貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。
[編輯本段]貪心演算法的基本思路
1.建立數學模型來描述問題。 2.把求解的問題分成若干個子問題。 3.對每一子問題求解，得到子問題的局部最優解。 4.把子問題的解局部最優解合成原來解問題的一個解。 實現該演算法的過程： 從問題的某一初始解出發； while 能朝給定總目標前進一步 do 求出可行解的一個解元素； 由所有解元素組合成問題的一個可行解。 下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。
[編輯本段]例題分析
[背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。 要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 價值 10 40 30 50 35 40 30 分析： 目標函數： ∑pi最大 約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150) （1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？ （2）每次挑選所佔重量最小的物品裝入是否能得到最優解？ （3）每次選取單位重量價值最大的物品，成為解本題的策略。 值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。 貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。 可惜的是，它需要證明後才能真正運用到題目的演算法中。 一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。 對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下： （1）貪心策略：選取價值最大者。 反例： 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，則答案錯誤。 【注意：如果物品可以分割為任意大小，那麼策略3可得最優解】 對於選取單位重量價值最大的物品這個策略，可以再加一條優化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。 但是，如果題目是如下所示，這個策略就也不行了。 W=40 物品：A B C 重量：28 20 15 價值：28 20 15 附：本題是個NP問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃演算法後本題就有了新的解法。
[編輯本段]備注
貪心演算法當然也有正確的時候。求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法。 所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）
[編輯本段]附貪心演算法成功案例之一
馬踏棋盤的貪心演算法 123041-23 XX 【問題描述】 馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。 【初步設計】 首先這是一個搜索問題，運用深度優先搜索進行求解。演算法如下： 1、 輸入初始位置坐標x,y； 2、 步驟 c: 如果c> 64輸出一個解，返回上一步驟c-- (x,y) ← c 計算(x,y)的八個方位的子結點，選出那此可行的子結點 循環遍歷所有可行子結點，步驟c++重復2 顯然（2）是一個遞歸調用的過程，大致如下： void dfs(int x,int y,int count) { int i,tx,ty; if(count> N*N) { output_solution();//輸入一個解 return; }
❺ Leetcode 中 Jump Game II 為什麼用貪心演算法是對的，如何證明
如果你說的貪心是指
Jump Game II (最小步數到達終點，貪心) 【leetcode】
定義F(i,j)表示i步能否到達j，由題目性質知若F(i,j)=true則必有F(i,j-1)=true。
因此可以定義G(i)表示i步最遠能到的格子，又由題目性質知G(i-1)<G(i)。
因此答案是minimum on i such that G(i) = n。
再由題目性質，G(i) = max(x+A(x) | 1<=x<=G(i-1))
所以是對的。
一般的，沒有辦法證明貪心演算法是對的。
你看上面那麼多「由題目性質」就知道了，不同的貪心演算法的證明方法千奇百怪，充斥奇技淫巧，一般來說其證明遠比演算法本身難，具體參考《演算法導論》。
❻ 漫談演算法如何證明貪心演算法是最優 using exchange argument
這里主要是介紹一種證明貪心演算法是最優的一種方法：Exchange Argument （不知道應該怎麼翻譯到中文，交換參數？感覺聽起來挺別扭的，不像是一個方法的名字~o( □ )o）
Exchange Argument的主要的思想也就是 先假設 存在一個最優的演算法和我們的貪心演算法最接近，然後通過交換兩個演算法里的一個步驟(或元素)，得到一個新的最優的演算法，同時這個演算法比前一個最優演算法更接近於我們的貪心演算法，從而得到矛盾，原命題成立。
下面來看一個更為formal的解釋：
步驟：
Step0: 給出貪心演算法A的描述
Step1: 假設O是和A最相似(假設O和A的前k個步驟都相同，第k+1個開始不同，通常這個臨界的元素最重要)的最優演算法
Step2: [Key] 修改演算法O(用Exchange Argument，交換A和O中的一個元素)，得到新的演算法O』
Step3: 證明O』 是feasible的，也就是O』是對的
Step4: 證明O』至少和O一樣，即O』也是最優的
Step5: 得到矛盾，因為O』 比O 更和A 相似。
證畢。
當然上面的步驟還有一個變種，如下：
Step0: 給出貪心演算法A的描述
Step1: 假設O是一個最優演算法（隨便選，arbitrary）
Step2: 找出O和A中的一個不同。（當然這裡面的不同可以是一個元素在O不再A，或者是一個pair的順序在A的和在O的不一樣。這個要根據具體題目）
Step3：Exchange這個不同的東西，然後argue現在得到的演算法O 不必O差。
Step4: Argue 這樣的不同一共有Polynomial個，然後我exchange Polynomial次就可以消除所有的不同，同時保證了演算法的質量不比O差。這也就是說A 是as good as 一個O的。因為O是arbitrary選的，所以A是optimal的。
證畢
下面給幾個例子：
例 Maximum Cardinality Disjoint Interval Problem
問題描述：給一些時間片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一個元素個數最多的子集S，子集中的每個元素的時間片段沒有交叉。
Greedy Algorithm: 每次都選所有interval 中bi最小的那個，把（ai，bi）加入S，然後把（ai，bi）在T中刪除，同時把T中所有和（ai，bi）有交叉的interval刪除，然後再在T中找最小的bj，循環上面的操作，直到沒有可以在添加的。
證明上面說的Greedy Algorithm是最優的。
下面就用第一個證明的步驟來證。
我們的Greedy Algorithm記為A，假設A不是最優的，那麼就一定存在一個O，O是和A最相近的一個最優的演算法，最相近是指和O和A的前K-1個選擇都相同，第K個是不同的。
假設對於A，A第k個選擇的是（ai，bi）；而O第K個選擇的是（aj，bj）。從A的定義我們可以直到，bi<=bj。
❼ 貪心演算法的本質
1. 貪心法（Greedy Algorithm）定義
求解最優化問題的演算法通常需要經過一系列的步驟，在每個步驟都面臨多種選擇；
貪心法就是這樣的演算法：它在每個決策點作出在當時看來最佳的選擇，即總是遵循某種規則，做出局部最優的選擇，以推導出全局最優解（局部最優解->全局最優解）
2. 對貪心法的深入理解
（1）原理：一種啟發式策略，在每個決策點作出在當時看來最佳的選擇
（2）求解最優化問題的兩個關鍵要素：貪心選擇性質+最優子結構
①貪心選擇性質：進行選擇時，直接做出在當前問題中看來最優的選擇，而不必考慮子問題的解；
②最優子結構：如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質
（3）解題關鍵：貪心策略的選擇
貪心演算法不是對所有問題都能得到整體最優解的，因此選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
（4）一般步驟：
①建立數學模型來描述最優化問題；
②把求解的最優化問題轉化為這樣的形式：對其做出一次選擇後，只剩下一個子問題需要求解；
③證明做出貪心選擇後：
1°原問題總是存在全局最優解，即貪心選擇始終安全；
2°剩餘子問題的局部最優解與貪心選擇組合，即可得到原問題的全局最優解。
並完成2°
3. 貪心法與動態規劃
最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。
❽ 貪心演算法中，通常會讓證明貪心選擇性，請問，證明貪心選擇性的實質是什麼怎樣說明一個問題具有貪心選擇呢
一般都是要最省事的比如
設有n中不同面值的硬幣，個硬幣的面值春雨數組T[1：n]中，現在要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存於數組Coins[1:n]中。
對任意簽署0<=m<=20001，設計一個用最少硬幣找錢m的方法。
用貪心演算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。這樣最少
程序實例
#include<stdio.h>
void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;
}
for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d張\n",T[i],coins[i]);
printf("\n");
}
❾ 貪心演算法的證明過程，是不是只有先證明了貪心選擇性質之後，再以貪心選擇為前提證明其最優子結構
對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
證明的大致過程為：首先考察問題的一個整體最優解，並證明可修改這個最優解，使其以貪心選擇開始。做了貪心選擇後，原問題簡化為規模更小的類似子問題。然後用數學歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優解。其中，證明貪心選擇後的問題簡化為規模更小的類似子問題的關鍵在於利用該問題的最優子結構性質。
❿ [演算法] 貪心演算法證明思路
動態規劃和貪心演算法都需要問題具有最優子結構，但不同的是貪心 自頂向下 ，先做選擇再求解一個結果子問題，而動態規劃自底向上求解子問題，需要先求出子問題的最優解再做選擇。這是因為，動態規劃最優解有兩個子問題時，求解子問題 時有j-i-1種選擇，但貪心選擇特徵能夠使 其中一個子問題必定為空 ，這種子問題和選擇數目的減少使得子問題能夠自頂向下被解決。
a) 定義子問題空間，做出一個選擇從而產生一個或多個子問題。子問題空間的定義結合需要求解的目標和選擇後子問題的描述刻畫來考慮。
b) 利用「剪切-粘貼」證明作為最優解的組成部分的每個子問題的解也是它本身的最優解。如果子問題的解不是最優解，將其替換為對應的最優解從而一定能得到原問題一個更優的解，這與最初的解是原問題的最優解的前提假設矛盾，因此最優子結構得證。
貪心的本質是局部最優解能產生全局最優解，即產生兩個子問題 和 時，可以直接解決子問題 （在子問題 中，使用貪心策略選擇a作為局部最優解）然後對子問題 進行分解，最終可以合並為全局最優解。
因此，要證明貪心選擇性質只需要證明 存在一個最優解是通過當前貪心選擇策略得到的 ，反過來，即證明**通過非貪心策略得到的原問題的最優解中也一定包含局部最優解a。
定義通過非貪心策略的選擇可以得到的一個最優解A，將最優解中的元素和當前貪心策略會選擇的元素逐個交換後得到的解A'並不比
A差（假設貪心策略會選擇的元素在當前最優解中未被選擇，通過「剪切-粘貼」證明得到的仍是最優解），可以證明存在原問題的最優解可以通過貪心選擇得到。