第三次課貪心算法

第三次課貪心算法第一頁，共七十三頁，編輯于2023年，星期四第3章內容提綱3.1貪心算法的基本思想3.2刪數問題3.3裝箱問題第二頁，共七十三頁，編輯于2023年，星期四 顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。 當然，希望貪心算法得到的最終結果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。第三頁，共七十三頁，編輯于2023年，星期四活動安排問題

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。第四頁，共七十三頁，編輯于2023年，星期四活動安排問題設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。第五頁，共七十三頁，編輯于2023年，星期四活動安排問題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面給出解活動安排問題的貪心算法GreedySelector:各活動的起始時間和結束時間存儲于數組s和f中且按結束時間的非減序排列

第六頁，共七十三頁，編輯于2023年，星期四活動安排問題 由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

第七頁，共七十三頁，編輯于2023年，星期四算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。第八頁，共七十三頁，編輯于2023年，星期四活動安排問題

例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314第九頁，共七十三頁，編輯于2023年，星期四活動安排問題

算法greedySelector的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。第十頁，共七十三頁，編輯于2023年，星期四活動安排問題若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可以用數學歸納法證明。第十一頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質和最優(yōu)子結構性質。

第十二頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素1、貪心選擇性質所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。第十三頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素

當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。2、最優(yōu)子結構性質第十四頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。3、貪心算法與動態(tài)規(guī)劃算法的差異第十五頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。第十六頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

第十七頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 具體算法可描述如下頁：

用貪心算法解背包問題的基本步驟：第十八頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質。第十九頁，共七十三頁，編輯于2023年，星期四貪心算法的基本要素 對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。第二十頁，共七十三頁，編輯于2023年，星期四3.2刪數問題 給定一個高精度的正整數N（不超過240位），去掉任意S個數字后剩下的數字按原左右次序組成一個新的正整數。編程對于給定的N和S，尋找一種方案使得剩下的數字組成的新數最小示例：

N=178543，S=4

則結果為：13第二十一頁，共七十三頁，編輯于2023年，星期四算法分析N的存儲只能采用數組，可選擇字符數組；可采用貪心算法，即：共刪掉S個數，每一步刪掉一個數，并且總選擇一個使剩下的數最小的數符刪去。為了保證刪1個數符后的數最小，可以按照從高位到低位的方向收縮遞減區(qū)間，如果不存在遞減區(qū)間則刪尾數符；否則刪掉遞減區(qū)間的首字符，這樣形成一個新的數串。然后回到串首，重復上面的規(guī)則，刪下一個數符，。。。，直至刪除S個數符為止。第二十二頁，共七十三頁，編輯于2023年，星期四17854317543154314313第二十三頁，共七十三頁，編輯于2023年，星期四17853417534153413413第二十四頁，共七十三頁，編輯于2023年，星期四程序#include<iostream.h>#include<math.h>usingnamespacestd;ints;classnode{public: charc; node*next;};classquee{public: node*first;};第二十五頁，共七十三頁，編輯于2023年，星期四quee*init(){ charstr[250];quee*n;node*tmp;node*tail; n=newquee;n->first=NULL;cin>>str;cin>>s;inti=0; while(str[i]!='\0') { tmp=newnode; tmp->c=str[i];tmp->next=NULL; if(n->first==NULL) { n->first=tmp;tail=tmp; } else { tail->next=tmp;tail=tmp; } i++; } returnn;};第二十六頁，共七十三頁，編輯于2023年，星期四voiddel(quee*start,node*p){ node*x; x=start->first; if(x->next) { while(x->next!=p)x=x->next; } x->next=p->next; deletep;};第二十七頁，共七十三頁，編輯于2023年，星期四voidprint(quee*start){ node*tmp; if(start->first==NULL)return; tmp=start->first; while(tmp) { printf("%c",tmp->c); tmp=tmp->next; } printf("\n");};第二十八頁，共七十三頁，編輯于2023年，星期四node*find(quee*start){ node*tmp; tmp=start->first; while(tmp->next!=NULL&&tmp->c<=tmp->next->c) tmp=tmp->next; returntmp;};第二十九頁，共七十三頁，編輯于2023年，星期四intmain(intargc,char*argv[]){ quee*n; node*p; n=init(); while(s!=0) { p=find(n); del(n,p); s--; } print(n); return0;}第三十頁，共七十三頁，編輯于2023年，星期四3.3POJ1017Packets第三十一頁，共七十三頁，編輯于2023年，星期四Packets題意已知：有6*6的大箱子和1*1，2*2，3*3，4*4，5*5，6*6的木塊(平面)問：給定各種木塊的數目，求最少需要多少個大箱子來裝？例如：輸入：004001-〉輸出2輸入：751000-〉輸出1第三十二頁，共七十三頁，編輯于2023年，星期四Packets解題思想：貪心準則：先放大的，后放小的6*6的木塊每個占用一個箱子；5*5的木塊每個占用一個新箱子，余下11個1*1的空格；4*4的木塊每個占用一個新箱子，余下5個2*2的空格。4.3*3的木塊每4個占用新一個箱子，不足4個也占一個新箱子，分情況余下不同數目的空格；5.2*2的木塊先填空格，空格不足開新箱子，每9個2*2的木塊占一個新箱子；6.1*1的木塊先填空格，空格不足開新箱子，每36個占一個新箱子。第三十三頁，共七十三頁，編輯于2023年，星期四Packets假設6*6，5*5，4*4，3*3，2*2，1*1的箱子個數b6b5b4b3b2b1第三十四頁，共七十三頁，編輯于2023年，星期四Packets

4*4，5*5，6*6的塊單獨開新的箱子。每一個5*5的塊還能放下11個1*1的箱子。每一個4*4的塊還能放下5個2*2的箱子，或者放下20個1*1的箱子。4*4塊5*5塊6*6塊第三十五頁，共七十三頁，編輯于2023年，星期四

3*3的塊1-4塊占一個新箱子，一個箱子可放下4個3*3的塊。如果一個箱子放下了1個3*3的塊，則還可放下5個2*2的塊和7個1*1的塊?；蛘呖梢苑畔?7個1*1的塊。如果一個箱子放下了2個3*3的塊，則還可放下3個2*2的塊和6個1*1的塊。或者可以放下18個1*1的塊。如果一個箱子放下了3個3*3的塊，則還可放下1個2*2的塊和5個1*1的塊。或者可以放下9個1*1的塊。第三十六頁，共七十三頁，編輯于2023年，星期四PacketsnTotal-箱子數1）先放好所有6*6,5*5,4*4和3*3的木塊

nTotal=b6+b5+b4+(b3+3)/44*4,5*5,6*6單獨開新的箱子

3*3每1-4個占一個新箱子2）再把2*2的塞到放有3*3木塊的箱子里 intContain2[4]={0,5,3,1}; Contain2[i]表示當箱子里有i個3*3的木塊時，還能放下多少個2*2的木塊 3）考慮放有3*3的木塊的箱子在塞滿2*2的木后還能放多少個1*1的木塊： intContain1[4]={0,7,6,5};

Contain1[i]表示當箱子里有i個3*3的木塊，并且還填滿了2*2的木塊后，還能放下多少個1*1的木塊。第三十七頁，共七十三頁，編輯于2023年，星期四Packets

如果箱子里放1個3*3木塊，那么還能放5個2*2木塊,以及7個1*1木塊第三十八頁，共七十三頁，編輯于2023年，星期四Packets

如果箱子里放2個3*3木塊，那么還能放3個2*2木塊,以及6個1*1木塊第三十九頁，共七十三頁，編輯于2023年，星期四Packets

如果箱子里放3個3*3木塊，那么還能放1個2*2木塊,以及5個1*1木塊第四十頁，共七十三頁，編輯于2023年，星期四Packets 4)計算放好6*6,5*5,4*4,3*3后留下多少空格能放2*2

c2=b4*5+Contain2[b3%4];留下多少空格能放1*1 c1=b5*11+Contain1[b3%4](能放2*2的地方暫不考慮放1*1，因為如果c2〉b2則多余的b2-c2個位置可以放4*(b2-c2)個1*1的箱子)第四十一頁，共七十三頁，編輯于2023年，星期四Packets

5)放2*2，如果不夠放，就開新箱子，放完2*2，計算還剩多少空格能放1*1。

if(b2<=c2) c1+=(c2-b2)*4; else{ nTotal+=(b2-c2)/9;//每個空箱子可以放9個2*2 intr2=(b2-c2)%9; if(r2){ nTotal++; c1+=36-r2*4; } }第四十二頁，共七十三頁，編輯于2023年，星期四

6)放1*1并輸出結果

if(b1>c1){ nTotal+=(b1-c1)/36; if((b1-c1)%36) nTotal++; } cout<<nTotal<<endl;Packets第四十三頁，共七十三頁，編輯于2023年，星期四#include<iostream.h>intContain1[4]={0,7,6,5};intContain2[4]={0,5,3,1};intnTotal;voidmain(){intb1,b2,b3,b4,b5,b6;for(;;){cin>>b1>>b2>>b3>>b4>>b5>>b6;if(b1==0&&b2==0&&b3==0&&b4==0&&b5==0&&b6==0) break; nTotal=b6+b5+b4+b3/4; if(b3%4)nTotal++; intc1; //當前能放1*1木塊的空格數目

c1=b5*11; //每個放5*5的箱子，還能放11個1*1的木塊c1+=Contain1[b3%4]; //加上3*3箱子里能放的數目

intc2;//當前能放2*2木塊的空格數目（先不考慮將1*1的木塊放在 //2*2的空格里）

c2=b4*5; //每個放5*4的箱子，還能放5個2*2的木塊

c2+=Contain2[b3%4]; //加上3*3箱子里能放的數目第四十四頁，共七十三頁，編輯于2023年，星期四

if(b2<=c2) c1+=(c2-b2)*4; else{ nTotal+=(b2-c2)/9;//每個空箱子可以放9個2*2 intr2=(b2-c2)%9; if(r2){ nTotal++; c1+=36-r2*4; } } if(b1>c1){ nTotal+=(b1-c1)/36; if((b1-c1)%36) nTotal++; } cout<<nTotal<<endl;}}第四十五頁，共七十三頁，編輯于2023年，星期四〖案例3〗水位為使房屋買主可以評估洪水保險的開銷，一家真實的房地產公司提供了一種客戶端程序，此程序現實了可能被購買得房屋所在地區(qū)以100平方米為單位的海拔高度。雨水、雪水和管道破裂流出的水將會匯聚到海拔最低，因為水會從高處流向低處。為簡化問題，我們假設水沿著排水溝從高出流向低處，并且水不會被土地所吸收。第四十六頁，共七十三頁，編輯于2023年，星期四從天氣信息的檔案中，我們得知了一個區(qū)域的典型儲水量。作為預期的購房者，我們希望知道低處積水后的水位，以及完全被淹沒在水中的面積占此地區(qū)的百分比(也就是，10平方米的海拔高度嚴格低于水平面)。你被要求寫一個程序來給出結果。第四十七頁，共七十三頁，編輯于2023年，星期四輸入數據輸入包括區(qū)域描述所構成的一個序列。每個由一對整數m和n開始，每個都小于30，給定的區(qū)域都是100平方米。緊隨其后的是m行，每行n個整數，給出地區(qū)海平面，以主行序給出。高度的單位是米，分別用正數或者負數表明高于或低于海平面。每個區(qū)域最后一個值是一個整數，用以指出有多少立方米的水聚集到此區(qū)域。m和n為兩個0代表輸入結束。第四十八頁，共七十三頁，編輯于2023年，星期四輸出描述對每個區(qū)域，顯示區(qū)域編號(1,2,…)，水平面(以米為單位表示高于或低于海平面)以及此區(qū)域被水淹沒的面積，每個占一行。水位和被水淹沒面積的百分率顯示時保留2位小數每個區(qū)域輸出后跟一個空行。第四十九頁，共七十三頁，編輯于2023年，星期四樣例332537455112349483271000000Region1Waterlevelis46.67meters.66.67percentoftheregionisunderwater.第五十頁，共七十三頁，編輯于2023年，星期四解題思路由于題目中特別聲明水無論如何都會流到當前水面最低的地方，使得問題一下子簡化了。很容易想到以下貪心算法：（1）把每個格子的高度排序；（2）以低格子到高格子的順序填水，把水均勻的鋪在當前的水面上，并不斷更新當前水面面積，和剩余水量；（3）若剩余水量為0，輸出當前水面高度和水面覆蓋率。第五十一頁，共七十三頁，編輯于2023年，星期四注意1．水面每達到一個格子的高度，水面的面積也要隨之擴大；2．高度有負值，水面的初始高度是最低格子的高度而不是0；3．考慮好若干個格子高度相等的情況；4．每個格子的面積是100；5．沒有水時，覆蓋率為0；6．水若剛好達到一個格子的高度，此格子不算被水覆蓋；7．水面達到最高格子后，要把剩下的水均勻的鋪在整個區(qū)域上；8．注意浮點數的計算誤差，因為這個原因大家在POJ上都沒有通過此題:-<第五十二頁，共七十三頁，編輯于2023年，星期四#include<stdio.h>#include<stdlib.h>inth[1000000];//保存每個格子的高度值，因不知m和n的范圍，故設的比較大intcmp(constvoid*a,constvoid*b){return*((int*)a)-*((int*)b);}第五十三頁，共七十三頁，編輯于2023年，星期四main(){intt,m,n,nn; doublex,hw;inti;t=0;第五十四頁，共七十三頁，編輯于2023年，星期四

while(1){//輸入

scanf("%d%d",&n,&m);if(n==0&&m==0)break; t++;nn=m*n;for(i=0;i<nn;i++){scanf("%d",&h[i]);}scanf("%lf",&x);//排序

qsort(h,nn,sizeof(int),cmp);第五十五頁，共七十三頁，編輯于2023年，星期四

i=0;hw=h[0];if(x>0){for(i=1;i<nn;i++){//在高度相等的情況下，擴大水面面積

while(i<nn&&h[i]==h[i-1]){i++;}if(i==nn||x<=100*i*(h[i]-h[i-1]))break;//若剩

下的水不夠使水面達到下一格子的高度，退出

x-=i*(h[i]-h[i-1])*100;}hw=h[i-1];}第五十六頁，共七十三頁，編輯于2023年，星期四if(x>0){//若剩下水，就把它鋪在當前的范圍上

while(i<nn&&h[i]==h[i-1]){i++;}hw+=x/i/100;}//輸出結果

printf("Region%d\n",t);printf("Waterlevelis%.2fmeters.\n",hw);printf("%.2fpercentoftheregionisunderwater.\n\n",i*100/double(nn));}}第五十七頁，共七十三頁，編輯于2023年，星期四〖案例4〗埃及分數埃及同中國一樣，也是世界上文明的古國之一。古埃及人處理分數與眾不同，他們一般只用分子為1的分數，例如：用1／3＋1／15來表示2／5，用1／4＋1／7＋1／28表示3／7，等等。設計一個程序，把一個真分數表示為埃及分數之和的形式。第五十八頁，共七十三頁，編輯于2023年，星期四Input第一行:N表示有N組測試數據，每組測試數據為一行包含a,b(0〈a〈b〈1000)。Output每組測試數據若干個數，自小到大排列，依次是單位分數的分母。SampleInput11945SampleOutput5618第五十九頁，共七十三頁，編輯于2023年，星期四所謂埃及分數，是指分子為1的形式。古代埃及有一個非常奇怪的習慣，他們喜歡把一個分數表示為若干個分子為1的分數之和的形式。如，7/8=1/2+1/3+1/24。下面介紹其中一種算法――貪心算法。貪心算法是由數學家菲波那契提出的，基本思想是：設某個真分數的分子為A，分母為B；把B除以A的商的整數部分加1后的值作為埃及分數的某一個分母；將A乘以C減去B作為新的A；將B乘以C作為新的B；如果A大于1且能整除B，則最后一個分母為B/A；如果A＝1，則最后一個分母為B；否則轉步驟（2）。如：7/8=1/2+1/3+1/24第六十頁，共七十三頁，編輯于2023年，星期四解題步驟：用變量A表示分子，變量B表示分母；C=B\A+1A=A*C-B,B=B*C打印1/C若A>1且B/A=B\A，則C=B/A若A＝1，則C=B,打印1/C轉步驟（2）。第六十一頁，共七十三頁，編輯于2023年，星期四#include<stdio.h>#include<stdlib.h>intnum;inta,b;intc;intzc(inta,intb){intxx;xx=b/a;if(xx*a==b)return1;return0;};第六十二頁，共七十三頁，編輯于2023年，星期四voidcalab(){while(1){c=(b/a)+1;a=a*c-b;b=b*c;printf("%d",c);if(a>1&&zc(a,b)){printf("%d\n",b/a);break;}elseif(a==1){