從貪婪算法的定義能夠看出，貪婪法其實(shí)不是從整體上考慮問題，它所做出的選擇不過在某種意義上的局部最優(yōu)解，而由問題自己的特征決定了該題運(yùn)用貪婪算法能夠獲得最優(yōu)解。我們看看下邊的例子例1均分紙牌（NOIP2002tg）[問題描繪]有N堆紙牌，編號(hào)分別為1，2，,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌，而后挪動(dòng)。移牌規(guī)則為：在編號(hào)為1堆上取的紙牌，只好移到編號(hào)為2的堆上；在編號(hào)為N的堆上取的紙牌，只好移到編號(hào)為N-1的堆上；其余堆上取的紙牌，能夠移到相鄰左邊或右側(cè)的堆上。此刻要求找出一種挪動(dòng)方法，用最少的挪動(dòng)次數(shù)使每堆上紙牌數(shù)都同樣多。比如N=4，4堆紙牌數(shù)分別為：①9②8③17④6挪動(dòng)3次可達(dá)到目的：從③取4張牌放到④（981310）->從③取3張牌放到②（9111010）->從②取1張牌放到①（10101010）。[輸入]：鍵盤輸入文件名。文件格式：N（N堆紙牌，1<=N<=100）A1A2An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）[輸出]：輸出至屏幕。格式為：全部堆均達(dá)到相等時(shí)的最少挪動(dòng)次數(shù)。[輸入輸出樣例]：498176屏慕顯示：

3算法剖析：設(shè)a[i]為第i堆紙牌的張數(shù)（0<=i<=n），v為均分后每堆紙牌的張數(shù)，s為最小移到次數(shù)。我們用貪婪法，依照從左到右的次序挪動(dòng)紙牌。如第i堆(0<i<n)的紙牌數(shù)a[i]不等于均勻值，則挪動(dòng)一次(即s加1)，分兩種狀況挪動(dòng)：（1）若a[i]>v，則將a[i]-v張紙牌從第I堆挪動(dòng)到第I+1堆；（2）若a[i]<v，則將v-a[i]張紙牌從第I+1堆挪動(dòng)到第I堆；為了設(shè)計(jì)的方便，我們把這兩種狀況一致看作是將a[I]-v張牌從第I堆挪動(dòng)到第I+1堆；挪動(dòng)后有：a[I]:=v；a[I+1]:=a[I+1]+a[I]-v；在從第i+1堆中拿出紙牌增補(bǔ)第i堆的過程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(a[i+1]+a[i]-v<0)的狀況。如n=3，三堆紙牌數(shù)為（1，2，27）這時(shí)v=10，為了使第一堆數(shù)為10，要從第二堆移9張紙牌到第一堆，而第二堆只有2張紙牌可移，這能否是意味著方才使用的貪婪法是錯(cuò)誤的呢？我們持續(xù)按規(guī)則剖析移牌過程，從第二堆移出9張到第一堆后，第一堆有10張紙牌，第二堆剩下-7張紙牌，再從第三堆挪動(dòng)17張到第二堆，恰好三堆紙牌數(shù)都是10，最后結(jié)果是對(duì)的，從第二堆移出的牌都可以從第三堆獲得。我們在挪動(dòng)過程中，不過改變了挪動(dòng)的次序，而挪動(dòng)的次數(shù)不變，所以本題使用貪婪法是可行的。源程序：vari,n,s:integer;v:longint;a:array[1..100]oflongint;f:text;fil:string;beginreadln(fil);assign(f,fil);reset(f);readln(f,n);v:=0;fori:=1tondobeginread(f,a[i]);inc(v,a[i]);end;v:=vdivn;{

每堆牌的均勻數(shù)

}fori:=1ton-1doifa[i]<>vthen{

貪婪選擇

}begininc(s);{移牌步數(shù)計(jì)數(shù)a[i+1]:=a[i+1]+a[i]-v;{end;{then}writeln(s);end.

}

使第

i

堆牌數(shù)為

v}利用貪婪算法解題，需要解決兩個(gè)問題：一是問題能否合適用貪婪法求解。我們看一個(gè)找?guī)诺睦?假如一個(gè)錢幣系統(tǒng)有3種幣值,面值分別為一角、五分和一分，求最小找?guī)艛?shù)時(shí)，能夠用貪婪法求解；假如將這三種幣值改為一角一分、五分和一分，就不能使用貪婪法求解。用貪婪法解題很方便，但它的合用范圍很小，判斷一個(gè)問題能否合適用貪婪法求解，目前還沒有一個(gè)通用的方法，在信息學(xué)比賽中，需要憑個(gè)人的經(jīng)驗(yàn)來判斷何時(shí)該使用貪婪算法。二是確立了能夠用貪婪算法以后，怎樣選擇一個(gè)貪婪標(biāo)準(zhǔn)，才能保證獲得問題的最優(yōu)解。在選擇貪婪標(biāo)準(zhǔn)時(shí)，我們要對(duì)所選的貪婪標(biāo)準(zhǔn)進(jìn)行考證才能使用，不要被表面上看似正確的貪婪標(biāo)準(zhǔn)所誘惑，以下邊的列子。例2（NOIP1998tg）設(shè)有n個(gè)正整數(shù)，將他們連結(jié)成一排，構(gòu)成一個(gè)最大的多位整數(shù)。比如:n=3時(shí)，3個(gè)整數(shù)13,312,343,連成的最大整數(shù)為:又如:n=4時(shí),4個(gè)整數(shù)7,13,4,246連結(jié)成的最大整數(shù)為7424613輸入：NN個(gè)數(shù)輸出:連結(jié)成的多位數(shù)算法剖析：本題很簡單想到使用貪婪法，在考試時(shí)有好多同學(xué)把整數(shù)按從大到小的次序連結(jié)起來，測試題目的例子也都切合，但最后測試的結(jié)果卻不全對(duì)。按這類貪婪標(biāo)準(zhǔn)，我們很簡單找到反例：12，121應(yīng)當(dāng)構(gòu)成12121而非12112,那么能否是互相包括的時(shí)候就從小到大呢？也不必定，如：12，123就是12312而非12112,這樣狀況就有好多種了。能否是本題不可以用貪婪法呢？其實(shí)本題是能夠用貪婪法來求解，不過方才的貪婪標(biāo)準(zhǔn)不對(duì)，正確的貪婪標(biāo)準(zhǔn)是：先把整數(shù)化成字符串，而后再比較a+b和b+a，假如a+b>b+a，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在b的后邊。源程序：vars:array[1..20]ofstring;t:string;i,j,k,n:longint;beginreadln(n);fori:=1tondobeginread(k);str(k,s[i]);end;fori:=1ton-1doforj:=i+1tondoifs[i]+s[j]<s[j]+s[i]thenbegin{互換}t:=s[i];s[i]:=s[j];s[j]:=t;end;fori:=1tondowrite(s[i]);end.貪婪算法所作的選擇能夠依靠于過去所作過的選擇，但決不依靠于未來的選擇，也不依靠于子問題的解，所以貪婪算法與其余算法對(duì)比擁有必定的速度優(yōu)勢。假如一個(gè)問題能夠同時(shí)用幾種方法解決，貪婪算法應(yīng)該是最好的選擇之一。貪婪算法經(jīng)典例子(2009-07-1510:17:04)標(biāo)簽：貪婪算法背包問題it分類：簡單算法一、定義什么是貪婪算法呢？所謂貪婪算法是指，在對(duì)問題求解時(shí)，老是做出在目前看來最好的選擇。也就是說，不從整體最優(yōu)解出發(fā)來考慮，它所做出的僅是在某種意義上的局部最優(yōu)解。貪婪算法不是對(duì)全部問題都能獲得整體最優(yōu)解，但對(duì)范圍相當(dāng)寬泛的很多問題都能產(chǎn)生整體最優(yōu)解或整體最優(yōu)解的近似解。貪婪算法的基本思路以下：成立數(shù)學(xué)模型來描繪問題。把求解的問題分紅若干個(gè)子問題。對(duì)每個(gè)子問題求解，獲得每個(gè)子問題的局部最優(yōu)解。把每個(gè)子問題的局部最優(yōu)解合成為本來問題的一個(gè)解。實(shí)現(xiàn)該算法的過程：從問題的某一初始狀態(tài)出發(fā)；while能朝給定總目標(biāo)行進(jìn)一步do求出可行解的一個(gè)解元素；由全部解元素組合成問題的一個(gè)可行解；二、例題剖析[背包問題]有一個(gè)背包，背包含量是M=150。有7個(gè)物件，物件能夠切割成隨意大小。要求盡可能讓裝入背包中的物件總價(jià)值最大，但不可以超出總?cè)萘俊Ｎ锛嗀BCDEFG重量35306050401025價(jià)值記適當(dāng)時(shí)學(xué)算法的時(shí)候，就是這個(gè)例子，能夠說很經(jīng)典。剖析：目標(biāo)函數(shù)：∑pi最大拘束條件是裝入的物件總重量不超出背包含量，即∑wi<=M(M=150)1）依據(jù)貪婪的策略，每次精選價(jià)值最大的物件裝入背包，獲得的結(jié)果能否最優(yōu)？2）每次精選所占重量最小的物件裝入能否能獲得最優(yōu)解？（3）每次選用單位重量價(jià)值最大的物件，成為解本題的策略?貪婪算法是很常有的算法之一，這是因?yàn)樗唵我仔?，結(jié)構(gòu)貪婪策略簡單。但是，它需要證明后才能真實(shí)運(yùn)用到題目的算法中。一般來說，貪婪算法的證明環(huán)繞著整個(gè)問題的最優(yōu)解必定由在貪婪策略中存在的子問題的最優(yōu)解得來的。關(guān)于本例題中的3種貪婪策略，都沒法成立，即沒法被證明，解說以下：（1）貪婪策略：選用價(jià)值最大者。反例：W=30物件：ABC重量：281212價(jià)值：302020依據(jù)策略，第一選用物件A，接下來就沒法再選用了，但是，選用B、C則更好。2）貪婪策略：選用重量最小。它的反例與第一種策略的反例差不多。3）貪婪策略：選用單位重量價(jià)值最大的物件。反例：W=30物件：ABC重量：282010價(jià)值：282010依據(jù)策略，三種物件單位重量價(jià)值同樣，程序沒法依照現(xiàn)有策略作出判斷，假如選擇A，則答案錯(cuò)誤。值得注意的是，貪婪算法其實(shí)不是完整不可以夠使用，貪婪策略一旦經(jīng)過證明成立后，它就是一種高效的算法。比方，求最小生成樹的Prim算法和Kruskal算法都是美麗的貪婪算法。［均分紙牌］有N堆紙牌，編號(hào)分別為1，2，，n。每堆上有若干張,但紙牌總數(shù)必為n的倍數(shù).能夠在任一堆上取若干張紙牌,而后挪動(dòng)。移牌的規(guī)則為：在編號(hào)為1上取的紙牌，只好移到編號(hào)為2的堆上；在編號(hào)為n的堆上取的紙牌，只好移到編號(hào)為n-1的堆上；其余堆上取的紙牌，能夠移到相鄰左側(cè)或右側(cè)的堆上。此刻要求找出一種挪動(dòng)方法，用最少的挪動(dòng)次數(shù)使每堆上紙牌數(shù)都同樣多。比如：n=4，4堆紙牌分別為：①9②8③17④6挪動(dòng)三次能夠達(dá)到目的：從③取4張牌放到④再從③區(qū)3張放到②而后從②去1張放到①。輸入輸出樣例：498176屏幕顯示：3算法剖析：設(shè)a[i]為第I堆紙牌的張數(shù)（0<=I<=n），v為均分后每堆紙牌的張數(shù)，s為最小挪動(dòng)次數(shù)。我們用貪婪算法，依照從左到右的次序挪動(dòng)紙牌。如第I堆的紙牌數(shù)不等于均勻值，則挪動(dòng)一次（即s加1），分兩種狀況挪動(dòng)：1．若a[i]>v，則將a[i]-v張從第I堆挪動(dòng)到第I+1堆；2．若

a[i]<v

，則將

v-a[i]

張從第

I+1

堆挪動(dòng)到第

I堆。為了設(shè)計(jì)的方便，我們把這兩種狀況一致看作是將挪動(dòng)后有a[i]=v;a[I+1]=a[I+1]+a[i]-v.

a[i]-v

從第

I堆挪動(dòng)到第

I+1

堆，在從第

I+1

堆拿出紙牌增補(bǔ)第

I堆的過程中可能回出現(xiàn)第

I+1

堆的紙牌小于零的狀況。如n=3，三堆指派數(shù)為到第一堆，而第二堆只有

1227，這時(shí)v=10，為了使第一堆為10，要從第二堆移2張能夠移，這能否是意味著方才使用貪婪法是錯(cuò)誤的呢？

9張我們持續(xù)按規(guī)則剖析移牌過程，從第二堆移出9張到第一堆后，第一堆有10張，第二堆剩下-7張，在從第三堆挪動(dòng)17張到第二堆，恰好三堆紙牌都是10，最后結(jié)果是對(duì)的，我們在挪動(dòng)過程中，不過改變了挪動(dòng)的次序，而挪動(dòng)次數(shù)不便，所以本題使用貪婪法可行的。Java源程序：publicclassGreedy{publicstaticvoidmain(String[]args){intn=0,avg=0,s=0;Scannerscanner=newScanner;ArrayList<Integer>array=newArrayList<Integer>( );"Pleaseinputthenumberofheaps:");n=( );"Pleaseinputheapnumber:");for(inti=0;i<n;i++){( ));}for(inti=0;i<( );i++){avg+=(i);}avg=avg/( );for(inti=0;i<( )-1;i++){s++;(i+1,(i+1)+(i)-avg);}"s:"+s);}}利用貪婪算法解題，需要解決兩個(gè)問題：一是問題能否合適用貪婪法求解。我們看一個(gè)找?guī)诺睦?，假如一個(gè)錢幣系統(tǒng)有三種幣值，面值分別為一角、五分和一分，求最小找?guī)艛?shù)時(shí)，能夠用貪婪法求解；假如將這三種幣值改為一角一分、五分和一分，就不可以使用貪婪法求解。用貪婪法解題很方便，但它的適用范圍很小，判斷一個(gè)問題能否合適用貪婪法求解，目前還沒有一個(gè)通用的方法，在信息學(xué)比賽中，需要憑個(gè)人的經(jīng)驗(yàn)來判斷。二是確立了能夠用貪婪算法以后，怎樣選擇一個(gè)貪婪標(biāo)準(zhǔn)，才能保證獲得問題的最優(yōu)解。在選擇貪婪標(biāo)準(zhǔn)時(shí)，我們要對(duì)所選的貪婪標(biāo)準(zhǔn)進(jìn)行考證才能使用，不要被表面上看似正確的貪婪標(biāo)準(zhǔn)所誘惑，以下邊的例子。［最大整數(shù)］設(shè)有n個(gè)正整數(shù)，將它們連結(jié)成一排，構(gòu)成一個(gè)最大的多位整數(shù)。比如：n=3時(shí)，3個(gè)整數(shù)13，312，343，連成的最大整數(shù)為。又如：n=4時(shí)，4個(gè)整數(shù)7，13，4，246，連成的最大整數(shù)為7424613。輸入：nN個(gè)數(shù)輸出：連成的多位數(shù)算法剖析：本題很簡單想到使用貪婪法，在考試時(shí)有好多同學(xué)把整數(shù)按從大到小的順序連結(jié)起來，測試題目的例子也都切合，但最后測試的結(jié)果卻不全對(duì)。按這類標(biāo)準(zhǔn)，我們很簡單找到反例：12，121應(yīng)當(dāng)構(gòu)成12121而非12112，那么能否是互相包括的時(shí)候就從小到大呢？也不必定，如12，123就是12312而非12123，這類狀況就有好多種了。能否是本題不可以用貪婪法呢？其實(shí)本題能夠用貪婪法來求解，不過方才的標(biāo)準(zhǔn)不對(duì)，正確的標(biāo)準(zhǔn)是：先把整數(shù)變換成字符串，而后在比較a+b和b+a，假如a+b>=b+a，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在b的后邊。java源程序：publicstaticvoidmain(String[]args){Stringstr="";ArrayList<String>array=newArrayList<String>( );Scannerin=newScanner;"Pleaseinputthenumberofdata:");intn=( );"Pleaseinputthedata:");while(n-->0){( ));}for(inti=0;i<( );i++)for(intj=i+1;j<( );j++){if((i)+(j))pareTo(j)+(i))<0){Stringtemp=(i);(i,(j));(j,temp);}}for(inti=0;i<( );i++){str+=(i);}"str=:"+str);}}貪婪算法所作的選擇能夠依靠于過去所作過的選擇，但決不依靠于未來的選擇，也不依靠于子問題的解，所以貪婪算法與其余算法對(duì)比擁有必定的速度優(yōu)勢。假如一個(gè)問題能夠同時(shí)用幾種方法解決，貪婪算法應(yīng)當(dāng)是最好的選擇之一。貪婪算法實(shí)例：找零錢（Java實(shí)現(xiàn)）珍藏/**********從桌面txt文件里讀取零錢數(shù)量以及需要找的錢總數(shù)而后利用貪婪算法求解之后從頭生成txt文件******************************************************************import.*;publicclassGreedySelect{publicGreedySelect(Stringfile)throwsIOException{try{=file;FileReaderreader=newFileReader(file);BufferedReaderBreader=newBufferedReader(reader);Strings=( );inti,j;change=newChange[10];intk=0;while(s!=null){j=0;i=0;String[]temp=newString[9];temp=("\\s");change[k]=newChange( );while(i<6){intnum=(temp[i]);if(num==0)j++;change[k].coins[i]=num;i++;}if(j==5)break;doublemoney=(temp[i])*100;change[k].money=(int)money;k++;s=( );}client=k-1;( );}catch(IOExceptione){( );}}publicvoidgreedySort( )oney;for(intj=5;j>=0;j--){if(j==5)temp=200;elseif(j==4)temp=100;elseif(j==3)temp=50;elseif(j==2)temp=20;elseif(j==1)temp=10;elseif(j==0)temp=5;if(money>=temp&&change[i].coins[j]>0){money-=temp;change[i].needCoins[j]++;change[i].coins[j]--;if(money>=temp&&change[i].coins[j]>0)j++;}}if(money!=0)change[i].successful=false;elsechange[i].successful=true;}}publicvoidsaveResult( )throwsIOExceptionuccessful){("顧客"+i+"需要"+change[i].money+"for(intj=0;j<6;j++){intk=change[i].needCoins[j];if(k>0)if(j==0)("五分:"+k);elseif(j==1)("一角:"+k);elseif(j==2)("兩角:"+k);elseif(j==3)("五角:"+k);elseif(j==4)("一元："+k);elseif(j==5)("一元："+k);

找零錢以下：

");}}else{("

顧客

"+i+"

沒法達(dá)成

");}}( );}catch(IOExceptione){( );}}privateintclient;privateChange[]change;privateStringfile;privateclassChange{publicChange( )點(diǎn)到終點(diǎn)的距離小于Ｎ，則加油次數(shù)k=0；始點(diǎn)到終點(diǎn)的距離大于N，加油站間的距離相等，即ａ[i]=a[j]=L=N，則加油次數(shù)最少k=n；加油站間的距離相等，即ａ[i]=a[j]=L>N，則不行能抵達(dá)終點(diǎn)；加油站間的距離相等，即ａ[i]=a[j]=L<N，則加油次數(shù)k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)；加油站間的距離不相等，即ａ[i]！=a[j]，則加油次數(shù)k經(jīng)過以下算法求解。（三）算法描繪貪婪算法的基本思想該題目求加油最少次數(shù)，即求最優(yōu)解的問題，可分紅幾個(gè)步驟，一般來說，每個(gè)步驟的最優(yōu)解不必定是整個(gè)問題的最優(yōu)解，但是關(guān)于有些問題，局部貪婪能夠獲得全局的最優(yōu)解。貪婪算法將問題的求解過程看作是一系列選擇，從問題的某一個(gè)初始解出發(fā)，向給定目標(biāo)推動(dòng)。推動(dòng)的每一階段不是依照某一個(gè)固定的遞推式，而是在每一個(gè)階段都看上去是一個(gè)最優(yōu)的決議（在必定的標(biāo)準(zhǔn)下）。不停地將問題實(shí)例概括為更小的相像的子問題，并希望做出的局部最優(yōu)的選擇產(chǎn)生一個(gè)全局得最優(yōu)解。貪婪算法的合用的問題貪婪算法合用的問題一定知足兩個(gè)屬性：（１）貪婪性質(zhì)：整體的最優(yōu)解可經(jīng)過一系列局部最優(yōu)解達(dá)到，而且每次的選擇能夠依靠從前做出的選擇，但不可以依靠于此后的選擇。（２）最優(yōu)子結(jié)構(gòu)：問題的整體最優(yōu)解包括著它的子問題的最優(yōu)解。貪婪算法的基本步驟（１）分解：將原問題分解為若干互相獨(dú)立的階段。（２）解決：關(guān)于每一個(gè)階段求局部的最優(yōu)解。（３）歸并：將各個(gè)階段的解歸并為原問題的解。[問題剖析]因?yàn)槠囀怯墒枷蚪K點(diǎn)方向開的,我們最大的麻煩就是不知道在哪個(gè)加油站加油能夠使我們既能夠抵達(dá)終點(diǎn)又能夠使我們加油次數(shù)最少。提出問題是解決的開始.為了著手解決碰到的困難,獲得最優(yōu)方案。我們能夠假定不到萬不得已我們不加油，即除非我們油箱里的油不足以開到下一個(gè)加油站，我們才加一次油。在局部找到一個(gè)最優(yōu)的解。卻每加一次油我們能夠看作是一個(gè)新的起點(diǎn)，用同樣的遞歸方法進(jìn)行下去。最后將各個(gè)階段的最優(yōu)解歸并為原問題的解獲得我們原問題的求解。加油站貪婪算法設(shè)計(jì)（C）：include<>include<>intadd(intb[],intm,intn){//求一個(gè)從m到n的數(shù)列的和intsb;for(inti=m;i<n;i++)sb+=b[i];returnsb;}intTanxin(inta[n],intN)

//a[n]

表示加油站的個(gè)數(shù)，

N為加滿油能行駛的最遠(yuǎn)距離{intb[n];

//若在

a[i]

加油站加油，則

b[i]

為1，不然為

0intm=0;if(a[i]>N)

return

ERROR;//

假如某相鄰的兩個(gè)加油站間的距離大于N，則不可以抵達(dá)終點(diǎn)if(add(a[i],0,n)<N){//假如這段距離小于N，則不需要加油b[i]=0;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]==N){//假如每相鄰的兩個(gè)加油站間的距離都是N，則每個(gè)加油站都需要加油b[i]=1;returnadd(b[i],0,n);}if(a[i]==a[j]&&a[i]<N){//假如每相鄰的兩個(gè)加油站間