算法設(shè)計技巧與分析講解材料

算法設(shè)計技巧與分析貪心算法—活動安排問題2025/1/181貪心算法貪心算法總是作出在當(dāng)前看來最好的選擇，也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。2025/1/182貪心算法貪心算法通常用于求解最優(yōu)化問題，即量的最大化或最小化問題。算法每一步工作較少且基于信息，因此特別有效。貪心算法通常包含一個用以尋找局部最優(yōu)解的迭代過程。其在少量計算的基礎(chǔ)上做出了正確猜想而且不考慮以后情況，一步步來構(gòu)筑解，每一次均建立在局部最優(yōu)解的基礎(chǔ)上。每一步同時又擴大了部分解的規(guī)模，做出的選擇產(chǎn)生最大的直接收益而又保持可行性。算法缺陷在于要證明該算法確實是求解了要解決的問題。2025/1/183貪心算法活動安排問題

活動安排問題是可以用貪心算法有效求解的一個很好的例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。貪心算法特性： 由一個簡單的迭代過程構(gòu)成，在維持可行性的前提下選擇產(chǎn)生最大直接利益的項。2025/1/184在下面所給出的解活動安排問題的貪心算法schedule中，各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f{中且按結(jié)束時間的非減序：.f1≦f2≦···≦fn排列。如果所給出的活動未按此序排列，我們可以用o(nlogn)的時間將它重排。

2025/1/186算法schedule中用集合a來存儲所選擇的活動?；顒觟在集合a中，當(dāng)且僅當(dāng)a[i]的值為true。變量n用以記錄最近一次加入到a中的活動。

貪心算法活動安排問題intschedule(ints[],intf[],boola[],intr){intn=1;intj=0;a[0]=true;for(inti=1;i<r;i++)2025/1/187貪心算法if(s[i]>=f[j]){a[i]=true;n++;j=i;}elsea[i]=false;cout<<"theleastamountmeetingplaceis:"<<n;returnn;}2025/1/188算法schedule中用集合a來存儲所選擇的活動?；顒觟在集合a中，當(dāng)且僅當(dāng)a[i]的值為true。變量n用以記錄最近一次加入到a中的活動。貪心算法schedule一開始選擇活動1，并將n初始化為1。然后依次檢查活動i是否與當(dāng)前已選擇的所有活動相容。若相容則將活動i加人到已選擇活動的集合a中，否則不選擇活動i，而繼續(xù)檢查下一活動與集合a中活動的相容性。2025/1/189完整程序

#include<iostream>usingnamespacestd;voidsort(intf[],intn){inttemp;for(inti=1;i<n;i++){

for(intj=0;j<i;j++)2025/1/1810if(f[j]>f[j+1]){temp=f[j];f[j]=f[j+1];f[j+1]=temp;}}cout<<"thesortresult:"<<endl;for(i=0;i<n;i++)cout<<f[i]<<",";cout<<endl;}2025/1/1811intschedule(ints[],intf[],boola[],intr){intn=1;intj=0;a[0]=true;for(inti=1;i<r;i++)if(s[i]>=f[j]){a[i]=true;n++;j=i;}elsea[i]=false;cout<<"theleastamountmeetingplaceis:"<<n;2025/1/1812returnn;}voidmain(){intr;//活動數(shù)

intp=0;cout<<"pleaseinputtheactivityquantity"<<endl;cin>>r;cout<<"pleaseinputthestart_time"<<endl;int*st=newint[r+1];bool*a=newbool[r+1];for(inti=0;i<r;i++)cin>>st[i];2025/1/1813cout<<"pleaseinputtheend_time"<<endl;int*et=newint[r+1];for(intj=0;j<r;j++)cin>>et[j];sort(et,r);schedule(st,et,a,r);cin