淺談貪心算法

《淺談貪心算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、貪心算法貪心算法是一種用來求最優(yōu)解的算法，主要思想是將問題分為數(shù)個步驟，用一個貪心標準逐步求出每一步驟的最優(yōu)解，最終產(chǎn)生全局最優(yōu)解。貪心算法的優(yōu)點是效率高，缺點是最終產(chǎn)生的解不一定是最優(yōu)解。1.均分絨牌（N0IP2002提壽組第1題）問題描述：有N堆紙牌，編號分別為1,2,…，No每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮疲缓笠苿?。移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或

2、右邊的堆上。現(xiàn)在要求用最少的移動次數(shù)S使每堆上紙牌數(shù)都一樣多。輸入格式：Na[l],a[2],…，a[N]輸出格式：S算凍分析：從第1堆到第N堆紙牌，按從左到右的順序，若第i堆紙牌數(shù)a[i]人于平均數(shù)k,則將多出的紙牌移到第1+1堆上；若a[i]小于k,則將缺少的紙牌數(shù)移到第1+1堆上（缺少的紙牌數(shù)可由右側(cè)傳遞給左側(cè)，次數(shù)相同）。例：n=4a[1..4]=461084——〉6——〉10——〉8-3-4-1（等于右給左2）（右給左4）（右給左1）嫄程序：Vara:Array[1..100]0fInteger

3、;i,n,t,s:Integer;BeginReadLn（n）;Fori:=1TonDoRead（a[i]）;Fori:=1TonDot:=t+a[i];t:=tDivn;｛求平均數(shù)｝Fori:=1Ton-1DoIfa[i]<>tThenBeginInc⑸；｛計數(shù)｝a[i+1]:=a[i+1]+(a[i]-t);End;WriteLn(s);End.在用貪心算法解題時，需要注意兩方面，一是問題是否適用于貪心算法，二是應(yīng)選用怎樣的貪心標準。在學(xué)習貪心法時，一定要多讀多練，才能進步。貪心題做得越多，理解越深，

4、思路越廣，利用貪心法解題的能力也就越強。1.部分背包問題問題描述：有一個容量為n的背包，有m件物品可供選擇，可以任意切割為整數(shù)個單位，它們的價值分別是v[l]—v[n],所占空間分別是w[l]—w[n],求怎樣選擇,所得物品總價值s最大。輸入格式：n,mv[l],v⑵,…，v[n]w[l],w[2],…，w[n]輸出格式：s算法分析：這是一道簡單的貪心題，可利用數(shù)組k記錄每個物品的單位價值，按價值排序，從人價值到小價值選擇，直到剩余空間n=0。需要注意整型與實型在使用上的細節(jié)。源程序：Vara,v,w:A

5、rray[1..100]0fInteger；k:Array[1..100]0fReal;i,j,n,m,t:lnteger;h,s:Real;BeginReadLn(n,m);Fori:=1TomDoRead(v[i]);Fori:=1TomDoRead(w[i]);Fori:=1TomDok[i]:=v[i]/w[i];｛求單位價值｝Fori:=1Tom-1DoForj:=i+1TomDoIfk[i]

6、:=v[j];vD]:=t;t：=w[i];w[i]:=w[j];w[j]:=t;End;｛排序｝Fori:=1TomDoBeginIfn=0ThenBreak；剩余空間，結(jié)束｝Ifw[i]<=nThenBeginn:=n-w[i];w[i]:=0;s:=s+v[i];v[i]：=0;k[i]：=0;EndElseBegins:=s+k[i]*n;Break;End;｛兩種情況｝End;WriteLn(s:0:2);End.1.牛奶問題問題描述：牛奶商總是希望花最少的成本，賺取最大的利潤。在一個牛奶采購市

7、場里，冇n個農(nóng)民，他們分別擁有k[l]…k[n]單位奶，單位價格分別是v[l]???v[n]。已知牛奶商需要m單位牛奶,假如他有無限的錢，應(yīng)該怎樣選擇，才會花費最少的錢s。輸入格式：n,mv[l],k[l]v[2],k[2]v[n],k[n]輸出格式：s算法分析：這道題與上一道題類似，先排序比較單位價格，再從低價到高價選擇，直到買完。源程序:Varv,k:Array[1..100]OfInteger;i,j,t,n,m:Integer;BeginReadLn(n,m);Fori:=1TonDoReadLn

8、(v[i],k[i]);Fori:=1Ton-1DoForj:=i+1TonDoIfv[i]>v[j]ThenBegint：=v[i];v[i]:=vD);v[j]:=t;t：=k[i];k[i]:=：=t;End;｛排序｝i:=0;t:=0;Whilem>0DoBeginlfi>nThenBeginWriteLn(tErrorl,);Exit;End;｛如果買完全部牛奶仍未滿足,則報錯｝lnc(i);Ifk[i]>=mThe