第三次課貪心算法

1、第三次課貪心算法第1頁，共73頁，2022年，5月20日，22點45分，星期六第3章 內(nèi)容提綱3.1 貪心算法的基本思想3.2 刪數(shù)問題3.3 裝箱問題第2頁，共73頁，2022年，5月20日，22點45分，星期六 顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。第3頁，共73

2、頁，2022年，5月20日，22點45分，星期六活動安排問題 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。第4頁，共73頁，2022年，5月20日，22點45分，星期六活動安排問題 設有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si fi 。如果選擇了活動i，則它在半開時間區(qū)間

3、si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。第5頁，共73頁，2022年，5月20日，22點45分，星期六活動安排問題templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; 下面給出解活動安排問題的貪心算法GreedySelector :各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間

4、的非減序排列 第6頁，共73頁，2022年，5月20日，22點45分，星期六活動安排問題 由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。 第7頁，共73頁，2022年，5月20日，22點45分，星期六 算法greedySelector的效率極高。當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的

5、活動未按非減序排列，可以用O(nlogn)的時間重排。 第8頁，共73頁，2022年，5月20日，22點45分，星期六活動安排問題 例：設待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：i1234567891011Si130535688212fi4567891011121314第9頁，共73頁，2022年，5月20日，22點45分，星期六活動安排問題 算法greedySelector 的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。第10頁，共73頁，2022年，5月20日，22點45

6、分，星期六活動安排問題 若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學歸納法證明。第11頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。 但是，從許多可以用貪心算法求解

7、的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 第12頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素1、貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體

8、最優(yōu)解。第13頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 2、最優(yōu)子結(jié)構(gòu)性質(zhì)第14頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主

9、要差別。3、貪心算法與動態(tài)規(guī)劃算法的差異第15頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素0-1背包問題： 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。第16頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1

10、in。 這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。 第17頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素 首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟：第18頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素

11、void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i=n;i+) xi=0; float c=M; for (i=1;ic) break; xi=1; c-=wi; if (i=n) xi=c/wi; 算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。第19頁，共73頁，2022年，5月20日，22點45分，星期六貪心算法的基本要素 對于0-1背包問題

12、，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。 第20頁，共73頁，2022年，5月20日，22點45分，星期六3.2 刪數(shù)問題給定一個高精度的正整數(shù)N（不超過240位），去掉任意S個數(shù)字后剩下的數(shù)字按原左右次序組成一個新的正整數(shù)。編程對于給定的N和S，尋找一種方案使得剩下的數(shù)字

13、組成的新數(shù)最小示例：N=178543， S=4則結(jié)果為：13第21頁，共73頁，2022年，5月20日，22點45分，星期六算法分析N的存儲只能采用數(shù)組，可選擇字符數(shù)組；可采用貪心算法，即：共刪掉S個數(shù)，每一步刪掉一個數(shù)，并且總選擇一個使剩下的數(shù)最小的數(shù)符刪去。為了保證刪1個數(shù)符后的數(shù)最小，可以按照從高位到低位的方向收縮遞減區(qū)間，如果不存在遞減區(qū)間則刪尾數(shù)符；否則刪掉遞減區(qū)間的首字符，這樣形成一個新的數(shù)串。然后回到串首，重復上面的規(guī)則，刪下一個數(shù)符，。，直至刪除S個數(shù)符為止。第22頁，共73頁，2022年，5月20日，22點45分，星期六17854317543154314313第23頁，共73

14、頁，2022年，5月20日，22點45分，星期六17853417534153413413第24頁，共73頁，2022年，5月20日，22點45分，星期六 程序#include #include using namespace std;int s;class nodepublic:char c;node *next;class queepublic:node *first;第25頁，共73頁，2022年，5月20日，22點45分，星期六quee *init()char str250; quee *n; node *tmp; node * tail;n=new quee; n-first=NULL

15、; cinstr; cins;int i=0;while(stri!=0)tmp=new node;tmp-c=stri; tmp-next=NULL;if(n-first=NULL)n-first=tmp; tail=tmp;elsetail-next=tmp; tail=tmp;i+;return n;第26頁，共73頁，2022年，5月20日，22點45分，星期六void del(quee *start, node *p)node *x;x=start-first;if (x-next)while(x-next!=p) x=x-next;x-next=p-next;delete p;第2

16、7頁，共73頁，2022年，5月20日，22點45分，星期六void print(quee *start)node *tmp;if(start-first=NULL) return;tmp=start-first;while(tmp)printf( %c,tmp-c);tmp=tmp-next;printf(n);第28頁，共73頁，2022年，5月20日，22點45分，星期六node *find(quee *start)node *tmp;tmp=start-first;while(tmp-next!=NULL & tmp-cnext-c)tmp=tmp-next;return tmp;第2

17、9頁，共73頁，2022年，5月20日，22點45分，星期六int main(int argc, char* argv)quee *n;node *p;n=init();while(s!=0)p=find(n);del(n,p);s-;print(n);return 0;第30頁，共73頁，2022年，5月20日，22點45分，星期六3.3 POJ 1017Packets第31頁，共73頁，2022年，5月20日，22點45分，星期六Packets題意已知：有6*6 的大箱子和 1*1，2*2，3*3，4*4，5*5，6*6 的木塊(平面)問：給定各種木塊的數(shù)目，求最少需要多少個大箱子來裝？例

18、如：輸入：0 0 4 0 0 1 - 輸出 2輸入：7 5 1 0 0 0 - 輸出 1第32頁，共73頁，2022年，5月20日，22點45分，星期六Packets解題思想： 貪心準則：先放大的，后放小的6*6的木塊每個占用一個箱子；5*5的木塊每個占用一個新箱子，余下11個1*1的空格；4*4的木塊每個占用一個新箱子，余下5個2*2的空格。4. 3*3的木塊每4個占用新一個箱子，不足4個也占一個新箱子，分情況余下不同數(shù)目的空格；5. 2*2的木塊先填空格，空格不足開新箱子，每9個2*2的木塊占一個新箱子；6. 1*1的木塊先填空格，空格不足開新箱子，每36個占一個新箱子。第33頁，共73頁

19、，2022年，5月20日，22點45分，星期六Packets假設 6*6，5*5，4*4 ，3*3，2*2，1*1的箱子個數(shù) b6 b5 b4 b3 b2 b1第34頁，共73頁，2022年，5月20日，22點45分，星期六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塊第35頁，共73頁，2022年，5月20日，22點45分，星期六 3*3的塊1-4塊占一個新箱子，一個箱子可放下4個3*3的塊。如果一個箱子放下了1個3*3的塊，則還可放下5個2*

20、2的塊和7個1*1的塊?；蛘呖梢苑畔?7個1*1的塊。如果一個箱子放下了2個3*3的塊，則還可放下3個2*2的塊和6個1*1的塊?；蛘呖梢苑畔?8個1*1的塊。如果一個箱子放下了3個3*3的塊，則還可放下1個2*2的塊和5個1*1的塊?；蛘呖梢苑畔?個1*1的塊。第36頁，共73頁，2022年，5月20日，22點45分，星期六PacketsnTotal - 箱子數(shù)1） 先放好所有 6 * 6, 5 * 5, 4 * 4 和3 * 3 的木塊nTotal = b6 + b5 + b4 + (b3+3)/4 4*4, 5*5, 6*6 單獨開新的箱子 3*3 每 1-4 個占一個新箱子 2）再把2

21、 * 2的塞到放有3*3木塊的箱子里 int Contain24 = 0, 5, 3, 1 ; Contain2i 表示當箱子里有i個 3*3的木塊時，還能放下多少個2*2的木塊3） 考慮放有3*3的木塊的箱子在塞滿2*2的木后還能放多少個1*1的木塊：int Contain14 = 0, 7, 6, 5 ; Contain1i 表示當箱子里有i個 3*3的木塊，并且還填滿了2*2的木塊后，還能放下多少個1*1的木塊。第37頁，共73頁，2022年，5月20日，22點45分，星期六Packets 如果箱子里放1個3*3木塊，那么還能放5個2*2木塊,以及7個1*1木塊第38頁，共73頁，202

22、2年，5月20日，22點45分，星期六Packets 如果箱子里放2個3*3木塊，那么還能放3個2*2木塊,以及6個1*1木塊第39頁，共73頁，2022年，5月20日，22點45分，星期六Packets 如果箱子里放3個3*3木塊，那么還能放1個2*2木塊,以及5個1*1木塊第40頁，共73頁，2022年，5月20日，22點45分，星期六Packets4) 計算放好6*6,5*5,4*4,3*3后留下多少空格能放2*2c2 = b4 * 5 + Contain2b3 % 4;留下多少空格能放1*1 c1 = b5 * 11 + Contain1b3 % 4 (能放2*2的地方暫不考慮放1*1

23、，因為如果c2b2則多余的b2-c2個位置可以放4*(b2-c2)個1*1的箱子)第41頁，共73頁，2022年，5月20日，22點45分，星期六Packets5) 放 2 * 2，如果不夠放，就開新箱子，放完2*2，計算還剩多少空格能放1*1。if ( b2 c1 ) nTotal += ( b1 - c1 ) / 36;if( b1 - c1) % 36 )nTotal +;cout nTotal endl;Packets第43頁，共73頁，2022年，5月20日，22點45分，星期六#include int Contain14 = 0, 7, 6, 5 ; int Contain24 =

24、 0, 5, 3, 1 ; int nTotal;void main() int b1,b2,b3,b4,b5,b6; for(;) cinb1b2b3b4b5b6; if(b1=0 & b2=0 & b3=0 & b4=0 & b5=0 & b6=0) break;nTotal = b6 + b5 + b4 + b3/ 4; if( b3 % 4) nTotal +;int c1; /當前能放 1*1 木塊的空格數(shù)目c1 = b5 * 11; /每個放5*5的箱子，還能放11個 1 * 1 的木塊c1 += Contain1b3 % 4 ; /加上3*3箱子里能放的數(shù)目int c2; /當前

25、能放 2*2 木塊的空格數(shù)目（先不考慮將1*1的木塊放在 / 2*2的空格里）c2 = b4 * 5; /每個放5*4的箱子，還能放5個 2 * 2 的木塊c2 += Contain2b3 % 4; /加上3*3箱子里能放的數(shù)目第44頁，共73頁，2022年，5月20日，22點45分，星期六if ( b2 c1 ) nTotal += ( b1 - c1 ) / 36;if( b1 - c1) % 36 )nTotal +;cout nTotal endl; 第45頁，共73頁，2022年，5月20日，22點45分，星期六案例3水位 為使房屋買主可以評估洪水保險的開銷，一家真實的房地產(chǎn)公司提供

26、了一種客戶端程序，此程序現(xiàn)實了可能被購買得房屋所在地區(qū)以100平方米為單位的海拔高度。雨水、雪水和管道破裂流出的水將會匯聚到海拔最低，因為水會從高處流向低處。為簡化問題，我們假設水沿著排水溝從高出流向低處，并且水不會被土地所吸收。第46頁，共73頁，2022年，5月20日，22點45分，星期六從天氣信息的檔案中，我們得知了一個區(qū)域的典型儲水量。作為預期的購房者，我們希望知道低處積水后的水位，以及完全被淹沒在水中的面積占此地區(qū)的百分比(也就是，10平方米的海拔高度嚴格低于水平面)。你被要求寫一個程序來給出結(jié)果。 第47頁，共73頁，2022年，5月20日，22點45分，星期六輸入數(shù)據(jù)輸入包括區(qū)域

27、描述所構(gòu)成的一個序列。每個由一對整數(shù)m和n開始，每個都小于30，給定的區(qū)域都是100平方米。緊隨其后的是m行，每行n個整數(shù)，給出地區(qū)海平面，以主行序給出。高度的單位是米，分別用正數(shù)或者負數(shù)表明高于或低于海平面。每個區(qū)域最后一個值是一個整數(shù)，用以指出有多少立方米的水聚集到此區(qū)域。m和n為兩個0代表輸入結(jié)束。第48頁，共73頁，2022年，5月20日，22點45分，星期六輸出描述對每個區(qū)域，顯示區(qū)域編號(1,2,)，水平面(以米為單位表示高于或低于海平面)以及此區(qū)域被水淹沒的面積，每個占一行。水位和被水淹沒面積的百分率顯示時保留2位小數(shù)每個區(qū)域輸出后跟一個空行。第49頁，共73頁，2022年，5月

28、20日，22點45分，星期六樣例3 325 37 4551 12 3494 83 27100000 0 Region 1Water level is 46.67 meters.66.67 percent of the region is under water.第50頁，共73頁，2022年，5月20日，22點45分，星期六解題思路由于題目中特別聲明水無論如何都會流到當前水面最低的地方，使得問題一下子簡化了。很容易想到以下貪心算法：（1）把每個格子的高度排序；（2）以低格子到高格子的順序填水，把水均勻的鋪在當前的水面上，并不斷更新當前水面面積，和剩余水量；（3）若剩余水量為0，輸出當前水面高度

29、和水面覆蓋率。第51頁，共73頁，2022年，5月20日，22點45分，星期六注意1水面每達到一個格子的高度，水面的面積也要隨之擴大；2高度有負值，水面的初始高度是最低格子的高度而不是0；3考慮好若干個格子高度相等的情況；4每個格子的面積是100；5沒有水時，覆蓋率為0；6水若剛好達到一個格子的高度，此格子不算被水覆蓋；7水面達到最高格子后，要把剩下的水均勻的鋪在整個區(qū)域上；8注意浮點數(shù)的計算誤差，因為這個原因大家在POJ上都沒有通過此題:- 第52頁，共73頁，2022年，5月20日，22點45分，星期六#include #include int h1000000; / 保存每個格子的高度值

30、，因不知m和n的范圍，故設的比較大int cmp(const void *a, const void *b) return *(int *)a) - *(int *)b);第53頁，共73頁，2022年，5月20日，22點45分，星期六main() int t, m, n, nn; double x, hw; int i; t = 0;第54頁，共73頁，2022年，5月20日，22點45分，星期六 while(1) /輸入 scanf(%d%d, &n, &m); if(n = 0 & m = 0) break; t+; nn = m * n; for(i = 0; i 0) for(i =

31、 1; i nn; i+) /在高度相等的情況下，擴大水面面積 while(i nn & hi = hi - 1) i+; if(i = nn | x 0) / 若剩下水，就把它鋪在當前的范圍上 while(i 1且B/A=BA，則C=B/A若A1，則C=B,打印1/C轉(zhuǎn)步驟（2）。第61頁，共73頁，2022年，5月20日，22點45分，星期六#include #include int num;int a,b;int c;int zc(int a,int b) int xx; xx=b/a; if(xx*a=b) return 1; return 0;第62頁，共73頁，2022年，5月20日，22點45分，星期六void calab() while(1) c=(b/a)+1; a=a*c-b; b=b*c; printf(%d,c); if(a1 & zc(a,b) printf(%dn,b/a); break; else if(a=1) printf(%dn,b); break; ;第63頁，共73頁，2022年，5月20日，22點45分，星期六main() int i; scanf(%dn,&num); for(i=1;i=num;i+) scanf(%d %dn,&a,&b); calab(); 第64頁，共73頁，2022年，5月20日，22點45分，星期六