c語言程序設計——貪心算法

1、貪心法的基本思想貪心法的基本思想例1:日常生活中經常會碰到找硬幣的例子?，F(xiàn)有四種硬幣，它們的面值分別是1元，5角，1角和1分?，F(xiàn)在要給顧客2元1角3分錢。如何找使得所拿出的硬幣個數(shù)最少? 貪心法 貪心法將一個最優(yōu)決策過程變成多步決策過程,并在每步總是做出當前看來是最好的選擇。貪心算法并不從全局最優(yōu)上加以考慮,它所做的選擇只是在某種意義上的局部最優(yōu)選擇。例2:如果硬幣的幣值改為1分,5分,1角1分三種,現(xiàn)要找給顧客1角5分? 1個1角1分+4個1分?貪心算法的定義 在求最優(yōu)解問題的過程中，依據(jù)某種貪心標準，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)

2、解，這種求解方法就是貪心算法。部分背包問題問題描述算法描述算法證明算法分析問題描述問題：給定問題：給定n種不同物品和一個背包，背包容種不同物品和一個背包，背包容量為量為M，物品，物品i的重量是的重量是Wi，裝物品，裝物品i的利潤是的利潤是Pi ，假定物品，假定物品i的一部分的一部分xi(0 xi 1),放進放進背包背包,得到利潤得到利潤Pi xi 問：應該如何裝包，才能獲得最大利潤？問：應該如何裝包，才能獲得最大利潤？問題描述給定給定M0，Wi0，Pi0， 1 i n，要求找一個，要求找一個n元元向量向量(x1,x2,xn)， 0 xi 1， 1 i n，使得，使得 n Pixi i=1達到最

3、大，同時滿足達到最大，同時滿足 n WixiM i=1 算法描述例 給定n=3,M=40, (W1,W2,W3)= (28,15,24), (P1,P2,P3)=(35,25,24)。五個可能的解如下： (x1,x2,x3) WixiM Pixi1 (1,4/5,0) 40 55 先裝利潤最大2 (1/2,1,1/3) 37 50.53 (1/28,1,1) 40 50.25 先裝重量最小4 (5/7,1,5/24) 40 55(25/28,1,0) 40 56.25 先裝利潤重量5 比值最大算法描述背包問題的貪心算法背包問題的貪心算法輸入：輸入：P(1:n),W(1:n),M，按，按P(i)

4、/W(i) P(i+1)/W(i+1)的順序讀入的順序讀入輸出：輸出：X(1:n)Procedure GREEDY-KNAPSACKreal:P(1:n) ,W(1:n),X(1:n),M,CU;Integer:i,n;begin1.Read (P(1:n).W(1:n),M);/設按設按P(i)/W(i) P(i+1)/W(i+1)的順序讀入的順序讀入/2.for i=1 to n do3. X(i)=0;/X(i)賦初值賦初值/4.CU=M;/CU是背包問題的剩余容量是背包問題的剩余容量/5.I:=1;6.while WI CU do begin7. XI:=1;8. CU:=CU-WI,

5、9. I:=I+1 end;10.XI:=CU/WIend算法證明定理定理 如果如果P1/W1 P2/W2 Pn/Wn ，算，算法法 GREEDY_ KNAPSACK 產生背包問題的產生背包問題的一個最優(yōu)解。一個最優(yōu)解。證明：設證明：設(x1,x2,xn)是算法產生的一個解，不是算法產生的一個解，不失一般性，設存在某個失一般性，設存在某個j，1jn， x1 = x2 = = xj-1=1, 0 xj1， xj+1 = xj+2 = = xn =0。再設再設(x1,x2,xn)是一個最優(yōu)解，我們證是一個最優(yōu)解，我們證明明(x1,x2,xn) (x1,x2,xn)。若不然，必存在若不然，必存在k，

6、1kn, 1i xk 。此種情況下可得到。此種情況下可得到 k-1 k-1 Wixi+ Wkxk Wixi + Wkxk M i=1 i=1于是可以通過增大于是可以通過增大xk 的取值，減小的取值，減小xk+1, xk+2, xn的取值，構造優(yōu)于的取值，構造優(yōu)于(x1, x2,xn)的解。矛盾。的解。矛盾。2 xk xk 。此種情況下必有。此種情況下必有xk 1?？紤]到考慮到xi = xi (1i Wixi =M i=1 i=1說明說明 (x1, x2,xn)不是問題的解。矛盾。不是問題的解。矛盾。綜合綜合1和和2兩種情形，算法產生一個最優(yōu)解兩種情形，算法產生一個最優(yōu)解。算法分析時間復雜性時間

7、復雜性 O(n)空間復雜性空間復雜性 O(n)貪心法的基本思想一種多步決策方法一種多步決策方法每一步使目標函數(shù)值增加最快或最慢每一步使目標函數(shù)值增加最快或最慢選擇最優(yōu)化量度是方法的關鍵選擇最優(yōu)化量度是方法的關鍵貪心算法的基本要素 對于一個具體的問題，怎么知道是否可用對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最貪心算法解此問題，以及能否得到問題的最優(yōu)解呢優(yōu)解呢? ?這個問題很難給予肯定的回答。這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有題中看到這類問題一般具有2 2個重要的性質：個重要的性

8、質：貪心選擇性質貪心選擇性質和和最優(yōu)子結構性質最優(yōu)子結構性質。 171 1、貪心選擇性質、貪心選擇性質 所謂所謂貪心選擇性質貪心選擇性質是指所求問題的是指所求問題的整體最整體最優(yōu)解優(yōu)解可以通過一系列可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。別。 對于一個具體問題，要確定它是否具有貪對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)

9、解。最終導致問題的整體最優(yōu)解。 當一個問題的最優(yōu)解包含其子問題的當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)解時，稱此問題具有最優(yōu)子結構性質最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征規(guī)劃算法或貪心算法求解的關鍵特征。 2 2、最優(yōu)子結構性質、最優(yōu)子結構性質動態(tài)規(guī)劃和貪心算法都是一種遞推算法 均有局部最優(yōu)解來推導全局最優(yōu)解 不同點： 貪心算法： 1.貪心算法中，作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優(yōu)解推導下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。 2.由（1）中的介紹，可以知道貪

10、心法正確的條件是：每一步的最優(yōu)解一定包含上一步的最優(yōu)解。動態(tài)規(guī)劃算法： 1.全局最優(yōu)解中一定包含某個局部最優(yōu)解，但不一定包含前一個局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解 2.動態(tài)規(guī)劃的關鍵是狀態(tài)轉移方程，即如何由以求出的局部最優(yōu)解來推導全局最優(yōu)解 3.邊界條件：即最簡單的，可以直接得出的局部最優(yōu)解貪心算法每一步都做目前最好的選擇，不考慮下一步的選擇。動態(tài)規(guī)劃的子問題每一步求的最優(yōu)解影響下一個問題的最優(yōu)解。貪心算法是種策略，思想。它并沒有固定的模式動態(tài)規(guī)劃的思想是分治+解決冗余把一個復雜的問題分解成一塊一塊的小問題每一個小問題中得到最優(yōu)解再從這些最優(yōu)解中獲取更優(yōu)的答案 貪心算法和動態(tài)規(guī)劃算法都

11、要求問題具貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是有最優(yōu)子結構性質，這是2 2類算法的一個類算法的一個共同點。但是，對于具有共同點。但是，對于具有最優(yōu)子結構最優(yōu)子結構的問的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求題應該選用貪心算法還是動態(tài)規(guī)劃算法求解解? ?是否能用動態(tài)規(guī)劃算法求解的問題也是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解能用貪心算法求解? ?（例如“0-1背包問題”與“部分背包問題”）3、貪心算法與動態(tài)規(guī)劃算法的差異 0-1背包問題 給定一個最大載重量為M的卡車和N種動物。已知第i種動物的重量為Wi，其最大價值為Vi，設定M，Wi，Vi均為整數(shù)，編程確定一個裝貨方

12、案，使得裝入卡車中的所有動物總價值最大。算法?按貪心法,有反例.設N=3，卡車最大載重量是100，三種動物A、B、C的重量分別是40，50，70，其對應的總價值分別是90、100、150。使用貪心算法的關鍵：使用貪心算法的關鍵： 該題是否適合于用貪心策略求解 如何選擇貪心標準，以得到問題的最優(yōu)解例5: 排隊打水問題2有N個人排隊到R個水龍頭去打水，他們裝滿水桶的時間為T1，T2，Tn為整數(shù)且各不相等，應如何安排他們的打水順序才能使他們總的花費的時間最少（包括等待時間）？分析分析 由于排隊時，越靠前面的計算的次數(shù)越多，由于排隊時，越靠前面的計算的次數(shù)越多，顯然越小的排在越前面得出的結果越小顯然越

13、小的排在越前面得出的結果越?。梢杂脭?shù)學方法簡單證明，這里就不再（可以用數(shù)學方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，贅述），所以這道題可以用貪心法解答，基本步驟：基本步驟：將輸入的時間按從小到大排序；將輸入的時間按從小到大排序；將排序后的時間按順序依次放入每個水龍頭的隊將排序后的時間按順序依次放入每個水龍頭的隊列中；列中； 統(tǒng)計，輸出答案。統(tǒng)計，輸出答案?！纠?】設有n個正整數(shù)，將他們連接成一排，組成一個最大的多位整數(shù)。例如:n=3時，3個整數(shù)13,312,343,連成的最大整數(shù)為:34331213又如:n=4時,4個整數(shù)7,13,4,246連接成的最大整數(shù)為7424613輸入：N N個數(shù)輸出:連接成的多位數(shù)算法分析：此題很容易想到使用貪心法，但如何貪？整數(shù)按從大到小的順序連接起來，樣例符合。再想想，我們還是可以找到反例：12，121 應該組成12121而非12112。是不是此題不能用貪心法呢？正確的貪心標準是：先把