算法設(shè)計與分析：貪婪算法

算法設(shè)計與分析貪心算法基本思想貪心算法類似于分治算法和動態(tài)規(guī)劃，也是一種基于子問題思想的策略。貪心算法是一個分階段決策過程，在每個局部階段，貪心法都做出一個當前最優(yōu)的局部決策，并期望通過每次所做的局部最優(yōu)決策產(chǎn)生一個全局最優(yōu)解。找零錢問題：假設(shè)有面值為5元、2元、1元、5角、2角、1角的貨幣，需要找給顧客4元6角現(xiàn)金，使付出的貨幣的數(shù)量最少？貪心算法基本思想貪心算法的求解過程通常包括如下三個步驟：分解，將原問題求解過程劃分為連續(xù)的若干個決策階段。決策，在每一個階段依據(jù)貪心策略進行貪心決策，得到局部的最優(yōu)解，并縮小待求解問題的規(guī)模。合并，將各個階段的局部解合并為原問題的一個全局可行解。

貪心算法基本思想Greedy(C){//C是問題的輸入集合即候選集合S={};

//初始解集合為空集while(notSolution(S)){

//集合S沒有構(gòu)成問題的一個可行解x=Select(C);

//在候選集合C中做貪心決策S=S+{x};C=C-{Collection(x)};

//減去一個與x關(guān)聯(lián)的集合}returnS;}候選集合C是構(gòu)造問題的解（包括最優(yōu)解）的對象集合。解集合S表示問題的解，它隨著貪心選擇的進行不斷擴展，直到構(gòu)成一個滿足問題的完整解。選擇函數(shù)Select是貪心策略的實現(xiàn)過程，這是貪心法的關(guān)鍵。它指出哪個候選對象最有希望構(gòu)成問題的最優(yōu)解，選擇函數(shù)通常和目標函數(shù)有關(guān)。找零錢問題續(xù)：假設(shè)有面值為1.1元，5角和1角的貨幣，現(xiàn)在要找給顧客1元5角錢，怎么找使得硬幣數(shù)目最少？活動安排問題策略一：選擇具有最早開始時間，而且不與已安排的活動沖突的活動。策略二：選擇具有最短使用時間，而且不與已安排的活動沖突的活動。策略三：選擇具有最早結(jié)束時間，而且不與已安排的活動沖突的活動。E={(0,10),(2,5),(7,9)}E={(0,4),(3,5),(4,9)}

例：設(shè)待安排的11個活動信息如下表所示：i1234567891011s[i]130535688212f[i]456789101112131401234567891011121314i1234567891011s[i]103355688212f[i]4658791011121314活動安排問題解活動安排問題的貪心算法設(shè)計思路如下：

#include<stdio.h>#include<algorithm>#defineMaxEvent1000using

namespacestd;intgreedyEventSchedule(intn,int*timeStart,int*timeFinish){

inti,j,selected,ans=0;

//冒泡排序，使得活動按結(jié)束時間升序排列

for(i=0;i<n;i++)

for(j=0;j+1<n;j++)

if(timeFinish[j]>timeFinish[j+1]){swap(timeFinish[j],timeFinish[j+1]);swap(timeStart[j],timeStart[j+1]);//注意開始時間也需一致移動}selected=0;//選擇第一個活動ans=1;

for(i=1;i<n;i++)

if(timeStart[i]>=timeFinish[selected]){selected=i;//選擇相容的最早結(jié)束活動ans++;}

returnans;}活動安排問題

證明（數(shù)學歸納法）：

活動安排問題

證明（數(shù)學歸納法）：小數(shù)背包問題

小數(shù)背包問題小數(shù)背包問題數(shù)學模型：0-1背包問題數(shù)學模型：小數(shù)背包問題策略一：在不超出當前背包的剩余容量前提下，優(yōu)先選擇價值最大的物品，這樣使得裝入價值增長最快。策略二：在不超出當前背包的剩余容量前提下，優(yōu)先選擇重量最輕的物品，這樣使得背包容量增長最慢。策略三：在不超出當前背包的剩余容量前提下，優(yōu)先選擇價值率（價值除以重量）最大的物品，這樣使得背包中單位重量價值增長最快。

例：n=3,c=20,v=(25,24,15),w=(18,15,10)策略一（1,2/15,0）2028.2策略二（0,2/3,1）2031策略三（0,1,1/2）2031.5小數(shù)背包問題小數(shù)背包問題的貪心算法設(shè)計思路如下：預(yù)處理，把物品按照價值率進行降序排列選擇第一個物品根據(jù)貪心策略，首先選擇價值率最大的物品，并記錄該物品裝入的重量。貪心選擇后續(xù)活動依次掃描每一個物品，在沒有超出背包容量的條件下，盡可能多地裝入當前價值率最高的物品，并記錄該物品裝入的重量。小數(shù)背包問題#include<stdio.h>#include<algorithm>using

namespacestd;#defineMaxItems1000structitem{

intweight;

intvalue;

bool

operator<(constitem&bb)const{//定義比較函數(shù)（小于號）

returnvalue/(1.0*weight)>(1.0*bb.value)/bb.weight;//為什么乘以1.0？}};//定義物品的結(jié)構(gòu)體doublegreedyKnapsack(intn,intcapacity,item*itemSet){

doubleans=0;sort(itemSet,itemSet+n);//STL中的快速排序算法

for(inti=0;i<n;i++)

if(capacity>=itemSet[i].weight){ans+=itemSet[i].value;//選擇單價最大的物品capacity-=itemSet[i].weight;}else{ans+=capacity*(itemSet[i].value*1.0)/itemSet[i].weight;//最后一個物品只能裝部分

break;}

returnans;}0-1背包問題與小數(shù)背包問題102030501.￥602.￥1003.￥1204.背包120

——×2030

1002012030220

601010020160

？601010020240

8020二元前綴碼定義二元前綴碼在一個字符集的編碼表（每一個編碼都表示為0-1字符串）中，如果任何一個字符編碼都不是其它字符編碼的前綴，則該編碼稱為二元前綴碼編碼把字符轉(zhuǎn)換為二元前綴碼的過程解碼

把二元前綴碼（0-1符號串）映射為字符的過程。從第一個字符開始依次讀入每個字符（0或者1），如果發(fā)現(xiàn)讀到的子串與某個代碼相等，就將這個字串譯作相應(yīng)代碼的字符。考慮字符集C={a,b,c,d}，如果其代碼集合為Q={001,00,010,01}，容易驗證Q不是二元前綴碼。考慮編碼序列0100001，存在兩種解碼方法：①解碼為01,00,001，譯碼為d，b，a②解碼為010，00，01，譯碼為c，b，d二元前綴碼定義二元前綴碼的存儲通常采用二叉樹結(jié)構(gòu)，令字符保存在葉節(jié)點，則該字符的前綴碼對應(yīng)根到該葉節(jié)點的一條路徑。規(guī)定每個節(jié)點通向左兒子的邊記為0，通向右兒子的邊記為1，則根到葉節(jié)點的路徑則可以轉(zhuǎn)換為一個0-1串，映射為二元前綴碼一個字符集可以構(gòu)造多個二元前綴碼a:000b:001c:010d:011e:100f:101a:0b:101c:100d:111e:1101f:1100最優(yōu)前綴碼怎么定義，怎么構(gòu)造？最優(yōu)前綴碼定義

最優(yōu)前綴碼則定義為平均碼長最小的二元前綴碼。定長編碼與變長編碼一個包含100,000個字符的文件，各字符出現(xiàn)頻率不同，如下表所示。不同的字符abcdef頻率(千次)4513121695定長編碼：用3位來表示一個字符，對整個文件編碼需要300,000位。定長碼000001010011100101變長碼010110011111011100變長編碼：給頻率高的字符較短的編碼；頻率低的字符較長的編碼，達到整體編碼減少的目的：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000哈夫曼編碼哈夫曼編碼算法的貪心策略是：給頻率高的字符較短的代碼；頻率低的字符較長的代碼把編碼映射成二叉樹，則其貪心策略可表述為：把頻率高的字符分配給靠近根結(jié)點（較淺）的葉結(jié)點，把頻率低的字符放置在遠離根結(jié)點（較深）的葉結(jié)點最優(yōu)前綴碼

#include<stdio.h>#include<vector>#include<queue>#include<algorithm>#include<iostream>#defineMaxChac1000using

namespacestd;structcmp{

bool

operator()(const

int&x,const

int&y){

returnx>y;

}};//定義優(yōu)先隊列需要的比較函數(shù)doublehaffmanCoding(intn,int*freq){

inti,total=0,sumFreq=0,jointFreq;priority_queue<int,vector<int>,cmp>heap;//優(yōu)先隊列，最小值優(yōu)先

for(i=0;i<n;i++){total+=freq[i];//頻次總和heap.push(freq[i]);}//形成優(yōu)先隊列

while(heap.size()>1){//循環(huán)選擇隊列中頻次最少的兩個元素合并jointFreq=0;//合并后結(jié)點的頻次

for(i=0;i<2;i++){//刪除頻次最少的兩元素jointFreq+=heap.top();heap.pop();}sumFreq+=jointFreq;heap.push(jointFreq);//優(yōu)先隊列中插入合并結(jié)點}

returnsumFreq/(1.0*total);//返回平均碼長}正確性證明交換論證法原理：從任意一個最優(yōu)解出發(fā)，經(jīng)過不斷用新的要素（符合貪心準則）替換解中的原有要素來改變這個解。通過有限步替換，把這個最優(yōu)解改變成貪心算法的解。如果替換過程中的每一步能保證解的最優(yōu)值不發(fā)生變化，則證明了貪心算法的解也是最優(yōu)的?；A(chǔ)步：給定任意一個最優(yōu)解，根據(jù)貪心準則對最優(yōu)解進行改造，也就是把第一步貪心選擇的對象替換最優(yōu)解中的特定要素，然后證明替換后的新解也是最優(yōu)解交換步：證明上述交換過程可以循環(huán)進行。也就是說，依次替換最優(yōu)解的其他要素，直到新解的每個分量都符合貪心準則，并且證明新解也是最優(yōu)的。證明方法一般是：最優(yōu)子結(jié)構(gòu)性質(zhì)+基礎(chǔ)步結(jié)論正確性證明─基礎(chǔ)步

正確性證明─交換步xyTzT’

與前提矛盾正確性證明─交換步xyTzT’

單源最短路徑問題描述：給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路徑長度，假設(shè)從源可以到達任何一個頂點。這里路徑的長度是指路徑上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。輸入：多組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行輸入圖G中頂點的個數(shù)n（n<1000）；后續(xù)n行n列輸入圖G的權(quán)值矩陣，其中第i行第j列的值表示從第i個頂點到第j個頂點的有向邊的權(quán)值，如果為-1表示從第i個頂點到第j個頂點沒有邊相連。默認第一個頂點為源。輸出：從源到所有其它各頂點的最短路徑長度之和。每組測試數(shù)據(jù)輸出一行。單源最短路徑從源到任意頂點的最短路徑具有類似于最優(yōu)子結(jié)構(gòu)性質(zhì)的特征：即最短路徑的子路徑也是源到相應(yīng)頂點的最短路徑。

單源最短路徑

循環(huán)StlowLR[A,B,C,D,E,F,G,H,I]0{}{0,99,99,99,99,99,99,99,99}1{A}A{0,9,2,6,99,99,99,99,99}2{A,C}C{0,9,2,5,99,3,99,99,99}3{A,C,F}F{0,9,2,4,99,3,99,99,9}4{A,C,F,D}D{0,6,2,4,11,3,13,99,9}5{A,C,F,D,B}B{0,6,2,4,10,3,13,99,9}6{A,C,F,D,B,I}I{0,6,2,4,10,3,13,14,9}7{A,C,F,D,B,I,E}E{0,6,2,4,10,3,11,14,9}8{A,C,F,D,B,I,E,G}G{0,6,2,4,10,3,11,12,9}Dijkstra算法1）設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)：帶權(quán)鄰接矩陣linkMatrix，記錄輸入有向圖的權(quán)值數(shù)組lowLR記錄從源到其它頂點的最短受限路徑長度數(shù)組preV記錄最短路徑中的前驅(qū)頂點，假設(shè)preV[x]=u，則在x的最短路徑中，u是x的前驅(qū)頂點2）初始化：把源加入集合S中，即S={v}，對于V-S中的所有頂點x，設(shè)置lowLR[x]=linkMatrix[v][x]，preV[x]=v（如果有邊相連）3）貪心選擇：在集合V-S中依照貪心策略尋找lowLR[x]最小的頂點

t，即

4）更新過程：將頂點

t加入S中，同時更新集合V-S，以及集合中頂點的最短受限路徑：#defineINF0x03F3F3F3F//預(yù)定義的充分大的值#defineMaxV100intpreV[MaxV];//最短路徑樹中的前驅(qū)結(jié)點信息表intvisited[MaxV];//結(jié)點是否加入S的標記表，是未加入，為已加入voidDijkstra(intlinkMatrix[][MaxV],intlowLR[MaxV],intnumV,intbeginV){

inti,j,min,newCost;memset(visited,0,sizeof(visited));//初始化，所有結(jié)點未加入

//開始結(jié)點beginV加入Svisited[beginV]=1;

for(i=0;i<numV;i++){lowLR[i]=linkMatrix[beginV][i];preV[i]=beginV;}lowLR[beginV]=0;preV[beginV]=-1;//樹根的標記

intselectV=beginV;

for(i=1;i<numV;i++){

for(j=0;j<numV;j++){//更新受限路徑newCost=lowLR[selectV]+linkMatrix[selectV][j];

if(visited[j]==0&&newCost<lowLR[j]){lowLR[j]=newCost;preV[j]=selectV;

}}

min=INF;

for(j=0;j<numV;j++)//貪心選擇最短受限路徑

if(visited[j]==0&&lowLR[j]<min){min=lowLR[j];selectV=j;}visited[selectV]=1;//更新被選擇頂點的狀態(tài)

}}正確性證明證明（數(shù)學歸納法）：對執(zhí)行步數(shù)k進行歸納

最小生成樹

最小生成樹-MST性質(zhì)

最小生成樹-Prim算法

最小生成樹-Prim算法最小生成樹─Prim算法

#defineMaxV1000#defineINF0x03F3F3F3F//預(yù)定義的充分大的值intprim(intlinkMatrix[][MaxV],intnumV){

intvisited[MaxV]={0};//結(jié)點是否加入MST的標記表，是未加入，為已加入

intlowCost[MaxV],closest[MaxV];

inti,k;

intmin,costMST=0;visited[0]=1;//頂點加入MSTclosest[0]=-1;//樹根的標記

for(i=1;i<numV;i++){lowCost[i]=linkMatrix[0][i];closest[i]=0;}

for(i=0;i<numV-1;i++){min=INF;

intselectV=0;

for(k=1;k<numV;k++){//貪心選擇最短的邊

if(!visited[k]&&lowCost[k]<min){min=lowCost[k];selectV=k;}}costMST+=min;//更新MST樹權(quán)重visited[selectV]=1;

for(k=1;k<numV;k++)//更新信息

if(!visited[k]&&linkMatrix[selectV][k]<lowCost[k]){lowCost[k]=linkMatrix[selectV][k];closest[k]=selectV;}}

returncostMST;}正確性證明

最小生成樹-Kruskal算法

Kruskal算法俗稱避環(huán)法，該算法的實現(xiàn)關(guān)鍵是在加入邊時避免出現(xiàn)環(huán)路。那么，怎么判斷加入某條邊后圖T中不會出現(xiàn)回路？并查集概念并查集（Disjointset或者Union-findset）是一種樹型的數(shù)據(jù)結(jié)構(gòu)，常用于處理一些不相交集合（DisjointSets）的合并及查詢問題。它包含兩種基本操作：查詢（Find）：查詢某個元素在哪個集合里合并（Union）：合并兩個集合每個集合選定一個固定的元素作為該集合的代表，稱為代表元素，代表元素則用于標識整個集合每一個集合用樹表示，樹中的每一個節(jié)點保存著到其父節(jié)點的引用，每個集合的代表元素即是集合的根節(jié)點。雙親表示法：用數(shù)組father[]存儲整個并查集集合怎么表示？集合怎么存儲？12354father[1]=-1father[2]=1father[3]=1father[5]=3father[4]=5并查集的查詢查詢（Find）：根據(jù)其父節(jié)點的引用向根行進，到達樹根并返回代表元素即可intFind(intx){

intp=x;

while(father[p]>0)

p=father[p];

returnp;

//樹根結(jié)點，集合的代表元素}12…xO(n)并查集的合并合并（Union）：將兩棵樹合并到一起，即將一棵樹的根連接到另一棵樹的根intUnion(intx,inty){

intxRoot=Find(x);intyRoot=Find(y);father[yRoot]=xRoot;

returnxRoot;//代表元素}13245合并1和2合并1和3合并5和4合并5和3father[yRoot]=xRootorfather[xRoot]=yRoot并查集優(yōu)化策略（一）路徑壓縮是一種在執(zhí)行“查詢”時扁平化樹結(jié)構(gòu)的方法。該操作可以為后續(xù)查詢操作加速。路徑上的每個節(jié)點都可以直接連接到根上；遞歸地訪問當前結(jié)點到樹根的路徑，改變每一個結(jié)點的引用到根節(jié)點。intFind(intx){

intp=x;

while(father[p]>0)

p=father[p];//找到樹根

while(father[x]!=p&&

father[x]>0){

inttemp=father[x];

father[x]=p;//指向樹根x=temp;

}

returnp;}13245pre[4]=3pre[5]=4pre[4]=1pre[5]=1并查集優(yōu)化策略（二）

1235611father[1]=-3;voidUnion(intx,inty){

intxRoot=Find(x);

intyRoot=Find(y);

if(xRoot==yRoot)return;

if(-father[xRoot]>-father[yRoot]){

father[yRoot]=xRoot;

}

else{

if(father[xRoot]==father[yRoot])

father[yRoot]-=1;//相等時

father[xRoot]=yRoot;

}}123564871011并查集優(yōu)化策略（二）最小生成樹-Kruskal算法

最小生成樹-Kruskal算法structedge{

intx,y;

intw;};structnode{

intfather;

intheight;};nodejuSet[MaxV];//比較函數(shù)，按權(quán)值(相同則按x坐標)非降序排序int