【正文】 3,1} {0,1,1/2} {...} {1,2/15,0} 20 20 20 31 ... ... 算法設(shè)計(jì)與分析 貪心算法 void Knapsack(int n,float M,float v[ ],float w[ ] ,float x[ ]) { Sort(n, v, w,t)。 //按單位價(jià)值排序 / int i。 for (i =1。i = n。i++) x[i] = 0。 float c = M。 //c為 背包剩余空間 / for (i =1。i = n。i ++) { if (w[t[i]] c) break。 x[t[i]]= 1。 c= w[t[i]]。 } if(i= n) x[t[i]] = c/w[t[i]]。 } 背包問(wèn)題的貪心算法 算法設(shè)計(jì)與分析 貪心算法 算法分析 : 排序?yàn)橹饕惴〞r(shí)間 ,所以 T(n)=O(nlogn) 背包問(wèn)題中的物體不能分拆 ,只能整個(gè)裝入稱(chēng)為 01背包問(wèn)題 . 算法證明 :該算法能得到在最優(yōu)解 用貪心算法能得到 01背包的最優(yōu)解嗎 ? ? 首先計(jì)算每種物品單位重量的價(jià)值 Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò) C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿(mǎn)為止。 ? 具體算法可描述如下頁(yè)： ? void Knapsack(int n,float M,float v[],float w[],float x[]) ? { ? Sort(n,v,w)。 ? int i。 ? for (i=1。i=n。i++) x[i]=0。 ? float c=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的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為 O（ nlogn）。 為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì) 。 對(duì)于 01背包問(wèn)題 ，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿(mǎn)，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮 01背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用 動(dòng)態(tài)規(guī)劃算法 求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問(wèn)題。 思考題 ? 0/1背包問(wèn)題：在雜貨店比賽中你獲得了第一名 ，獎(jiǎng)品是一車(chē)免費(fèi)雜貨 。 店中有 n 種不同的貨物 。 規(guī)則規(guī)定從每種貨物中最多只能拿一件 ， 車(chē)子的容量為 c， 物品 i 需占用 wi 的空間 ， 價(jià)值為 pi。 你的目標(biāo)是使車(chē)中裝載的物品價(jià)值最大 。 當(dāng)然 ， 所裝貨物不能超過(guò)車(chē)的容量 ， 且同一種物品不得拿走多件 。如何選擇量度標(biāo)準(zhǔn)才能找到最優(yōu)解 ？ 算法設(shè)計(jì)與分析 貪心算法 思考題 找零錢(qián)問(wèn)題：一個(gè)小孩買(mǎi)了價(jià)值為 33美分的糖 ，并將 1美元的錢(qián)交給售貨員 。 售貨員希望用數(shù)目最少的硬幣找給小孩 。 假設(shè)提供了數(shù)目不限的面值為 25美分 、 10美分 、 5美分 、 及 1美分的硬幣 。 使用貪心算法求解最優(yōu)結(jié)果 。 并證明找零錢(qián)問(wèn)題的貪心算法總能產(chǎn)生具有最少硬幣數(shù)的零錢(qián) 。 算法設(shè)計(jì)與分析 貪心算法 問(wèn)題 :通訊過(guò)程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進(jìn)制碼 .由于英文字母使用頻率不同 ,若頻率高的字母對(duì)應(yīng)短的編碼 ,頻率低的字母對(duì)應(yīng)長(zhǎng)的編碼 ,傳輸?shù)臄?shù)據(jù)總量就會(huì)降低 .要求找到一個(gè)編碼方案 ,使傳輸?shù)臄?shù)據(jù)量最少 . 見(jiàn) P109表 41 算法設(shè)計(jì)與分析 貪心算法 前綴碼 為能正確譯碼 ,編碼需采用 前綴碼 , 對(duì)每一個(gè)字符規(guī)定一個(gè) 0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱(chēng)為前綴碼。 表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有 2個(gè)兒子結(jié)點(diǎn)。 平均碼長(zhǎng)定義為： 使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱(chēng)為給定編碼字符集C的最優(yōu)前綴碼。 哈夫曼編碼 )()()( cdcfTB TCc???算法思路： 1)以 n個(gè)字母為結(jié)點(diǎn)構(gòu)成 n棵僅含一個(gè)點(diǎn)的二叉樹(shù)集合 ,字母的頻率 即為結(jié)點(diǎn)的權(quán)． 2)每次從二叉樹(shù)集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹(shù) :增加一個(gè)根結(jié)點(diǎn)將這兩棵樹(shù)作為左右子樹(shù) .新樹(shù)的權(quán)為兩棵子樹(shù)的權(quán)之和 . 3) 反復(fù)進(jìn)行步驟 2)直到只剩一棵樹(shù)為止 . ? 構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱(chēng)為 哈夫曼編碼 。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹(shù) T。 算法以 |C|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行 |C|－ 1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹(shù) T。 算法設(shè)計(jì)與分析 貪心算法 哈夫曼編碼 templateclass T BinaryTreeintHuffmanTree(T f[], int n) {//根據(jù)權(quán) f[1:n]構(gòu)造霍夫曼樹(shù) //創(chuàng)建一個(gè)單節(jié)點(diǎn)樹(shù)的數(shù)組 Huffman T*W=newHuffmanT [n+1]； BinaryTreeint z,zero； for(int i=1； i=n； i++){ (i, zero, zero)； W[i].weight=f[i]； W[i].tree=z: } //數(shù)組變成 — 個(gè)最小堆 MinHeapHuffmanTQ(1)； (w,n,n)； //將堆中的樹(shù)不斷合并 HuffmanT x, y for(i=1。in。i++){ (x)； (y)； (0, , )； +=； =z； (x)； } Q. DeleteMin(x)； //最后的樹(shù) Q. Deactivate()； delete[] w； return ； 哈夫曼樹(shù)算法 算法設(shè)計(jì)與分析 貪心算法 哈夫曼編碼 在書(shū)上給出的算法 huffmanTree中，編碼字符集中每一字符 c的頻率是 f(c)。 以 f為鍵值的優(yōu)先隊(duì)列 Q用在貪心選擇 時(shí)有效地確定算法當(dāng)前要合并的 2棵具有最小頻率的樹(shù)。一旦 2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的 2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列 Q。經(jīng)過(guò) n－ 1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù) T。 算法 huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列 Q。初始化優(yōu)先隊(duì)列需要 O(n)計(jì)算時(shí)間，由于最小堆的removeMin和 put運(yùn)算均需 O(logn)時(shí)間， n－ 1次的合并總共需要 O(nlogn)計(jì)算時(shí)間。因此，關(guān)于 n個(gè)字符的哈夫曼算法的 計(jì)算時(shí)間 為 O(nlogn) 。 最優(yōu)子結(jié)構(gòu) : 設(shè) T為帶權(quán) w1≤w2≤... ≤wt的最優(yōu)樹(shù) ,若將以帶權(quán)w1和 w2的樹(shù)葉為兒子的分枝點(diǎn)改為帶權(quán) w1+w2的樹(shù)葉 ,得到一棵新樹(shù) T39。, 則 T39。也是最優(yōu)樹(shù)。 貪心選擇性 : 設(shè) T為帶權(quán) w1≤w2≤... ≤wt的最優(yōu)樹(shù) , a).帶權(quán) w1和 w2的樹(shù)葉 vw1和 vw2是兄弟 . b).以 vw1和 vw2為兒子的分枝點(diǎn) ,其通路長(zhǎng)度最長(zhǎng) . 算法證明 算法分析 HuffmanTree初始化優(yōu)先隊(duì)列 Q需要 O(n) DeleteMin和 Insert需 O(logn). n1次的合并總共需要 O(nlogn) 所以 n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為 O(nlogn) 算法設(shè)計(jì)與分析 貪心算法 哈夫曼編碼 單源最短路徑 問(wèn)題 : 給定帶權(quán)有向圖 G=(V,E), 其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù) .要計(jì)算從 V的一點(diǎn) v0(源 )到所有其他各頂點(diǎn)的最短路長(zhǎng)度 . 路長(zhǎng)指路上各邊權(quán)之和。 算法設(shè)計(jì)與分析 貪心算法 算法思路 (Dijkstra) :設(shè)最短路長(zhǎng)已知的終點(diǎn)集合為 S,初始時(shí) v0?S, 其最短路長(zhǎng)為 0,然后用 貪心選擇 逐步擴(kuò)充 S :每次在 VS中 ,選擇 路徑長(zhǎng)度值最小的一條最短路徑 的 終點(diǎn) x加入 S. 例 題 構(gòu)造路長(zhǎng)最短的最短路徑 :設(shè)已構(gòu)造 i條最短路徑 ,則下一個(gè)加入 S的終點(diǎn) u必是 VS中具有最小路徑長(zhǎng)度的終點(diǎn) , 其長(zhǎng)度或者是弧 (v0,u), 或者是中間只經(jīng)過(guò) S中的頂點(diǎn)而最后到達(dá)頂點(diǎn) u的路徑 . 例 題 已知一個(gè) n 結(jié)點(diǎn)的有向圖 G=(V,E)和邊的權(quán)函數(shù)c(e)， 求由 G中某指定結(jié)點(diǎn) v0到其他各個(gè)結(jié)點(diǎn)的最短路徑 。 v0 v2 v1 v3 v4 v5 20 45 50 10 15 15 20 10 35 30 3 路徑 長(zhǎng)度 (1) v0v2 10 (2) v0v2v3 25 (3) v0v2v3v1 45 (4) v0v4 45 算法設(shè)計(jì)與分析 貪心算法 產(chǎn)生最短路徑的貪心方法 ? 逐條構(gòu)造這些最短路徑， 使用迄今已生成的所有路徑長(zhǎng)度之和作為一種量度標(biāo)準(zhǔn) 。 ? 為了使這一量度達(dá)到最小，其單獨(dú)的每一條路徑都必須具有最小長(zhǎng)度。 ? 使用這標(biāo)準(zhǔn)時(shí)，假定已構(gòu)造了 i條最短路徑，則下面要構(gòu)造的路徑應(yīng)該是下一條最短的最小長(zhǎng)度路徑。 ? 生成從 v0到所有其它結(jié)點(diǎn)的最短路徑的貪心方法就是 按照路徑長(zhǎng)度的非降次序生成這些路徑 。 算法設(shè)計(jì)與分析 貪心算法 產(chǎn)生最短路徑的貪心方法 ? 設(shè) S表示對(duì)其已經(jīng)生成了最短路徑的那些結(jié)點(diǎn) (包括 v0)的集合。 ? 擴(kuò)張 S的過(guò)程：對(duì)于不在 S中的結(jié)點(diǎn) w，設(shè) DIST(w)是從 v0開(kāi)始只經(jīng)過(guò) S中的結(jié)點(diǎn)而在結(jié)點(diǎn) w結(jié)束的那條最短路徑的長(zhǎng)度，則有 ： – 如果下一條最短路徑是到結(jié)點(diǎn) u，則這條路徑是從 v0處開(kāi)始而在 u處終止，并且只通過(guò)那些在 S中的結(jié)點(diǎn)。 – 所生成的下一條路徑的終點(diǎn) u必定是所有不在 S內(nèi)的結(jié)點(diǎn)中具有最小距離 DIST(u)的結(jié)點(diǎn)。 算法設(shè)計(jì)與分析 貪心算法 產(chǎn)生最短路徑的貪心方法 ? 選出了結(jié)點(diǎn) u并生成了從 v0到 u的最短路徑之后，結(jié)點(diǎn) u就成為 S中的一個(gè)成員。 ? 此時(shí)，那些從 v0開(kāi)始，只通過(guò) S中的結(jié)點(diǎn)并且在 S外的結(jié)點(diǎn) w處結(jié)束的最短路徑可能會(huì)減小。 ? 如果長(zhǎng)度改變了，則它必定是由一條從 v0開(kāi)始，經(jīng)過(guò) u然后到 w的更短路徑所造成的。 ? 其中從 v0到 u的路徑是一條最短路徑，從 u到 w的路徑是邊u,w，于是這條路徑的長(zhǎng)度就是： DIST(u)+c(u,w) 算法設(shè)計(jì)與分析 貪心算法 算法設(shè)計(jì)與分析 貪心算法 算法描述 ： (1) 用帶權(quán)的鄰接矩陣 c來(lái)表示帶權(quán)有向圖 , c[i][j]表示弧 vi,vj 上的權(quán)值 . 若 vi, vj?V,則置 c[i][j]為 ? 設(shè) S為已知最短路徑的終點(diǎn)的集合 ,它的初始狀態(tài)為空集 . 從源點(diǎn) v到圖上其余各點(diǎn) vi的當(dāng)前最短路徑長(zhǎng)度的初值為： dist[i]=c[v][i] ， vi?V (2) 選擇 vj, 使得 dist[j]=Min{dist[i] | vi?VS} vj就是長(zhǎng)度最短的最短路徑的終點(diǎn)。令 S=SU{