算法設(shè)計(jì)（第6章貪心法）

1、算法設(shè)計(jì)（第算法設(shè)計(jì)（第6 6章貪心法章貪心法）貪心法簡(jiǎn)介找零錢問(wèn)題10元3元=7元: 5 + 2100元3元=97元: 50 + 20 + 20 + 5 + 2100元14元=86元: 50 + 20 + 10 + 5 + 1沒(méi)有更優(yōu)的找錢方案每次盡可能地選取最大面額的鈔票貪心法簡(jiǎn)介找零錢問(wèn)題每次盡可能地選取最大面額的鈔票貪心算法Algorithm Change(int x)begin let a1 = a2 = a3 = 0; if (x 5) then a3 1; x x 5; while (x 2) do a2 a2 + 1; x x 2; a1 x; return (a1, a2,

2、a3);end貪心法簡(jiǎn)介找零錢問(wèn)題最優(yōu)性證明：1假設(shè)x的值為1, 2, 5，那么所需的零錢為1張，這顯然是最少的。2否那么，所需的錢數(shù)至少為2張。算法對(duì)3, 4, 6, 7生成的找錢方案分別為2+1, 2+2, 5+1, 5+2，這顯然也是最少的。3假設(shè)x的值為8和9，算法生成的找錢方案分別為5+2+1和5+2+2；而用2張鈔票不能找出8元或9元的零錢，因此算法的結(jié)果也是最少的。 如果將x的值擴(kuò)大到100以內(nèi)，并增加面值為50, 20和10元的鈔票，那么使用貪心算法仍然能夠得到最優(yōu)的找錢方案， 即每次盡可能地選取最大面額的零鈔。每次盡可能地選取最大面額的鈔票貪心法簡(jiǎn)介貪心算法：在問(wèn)題求解的過(guò)程

3、中采用“貪婪的策略來(lái)構(gòu)造目標(biāo)解。實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單難點(diǎn)通常在于算法的正確性證明貪心法簡(jiǎn)介最大裝載問(wèn)題輸入：總重量限制W，以及n個(gè)物品的重量A = a0, a1, ,an1輸出：A的一個(gè)子集A*，其和不大于W，且元素?cái)?shù)量盡可能大W = 1000, A = 400, 350, 300, 250, 240, 180, 150, 120選取選取 120 + 150 + 180 + 240 + 250最優(yōu)不可能選出5個(gè)以上的物品每次盡可能地選取重量最小的物品貪心法簡(jiǎn)介每次盡可能地選取重量最小的物品貪心算法Algorithm MaxLoad(W: int; A: int)begin Sort(A); let

4、 i = 0; while (W0) do if (Ai W) then W W - Ai; i i + 1; return A0.i;end最大裝載問(wèn)題貪心法簡(jiǎn)介最優(yōu)性證明：【引理6.1】設(shè)A*是問(wèn)題P(A,W)的一個(gè)最優(yōu)解，那么a0總是可以包含在A*中。【引理6.2】設(shè)A*是問(wèn)題P(A,W)的一個(gè)最優(yōu)解，且a0A*，那么A*a0也是問(wèn)題P(Aa0,Wa0)的一個(gè)最優(yōu)解?！径ɡ?.1】貪心算法6.2輸出最大數(shù)量裝載問(wèn)題P(A,W)的一個(gè)最優(yōu)解。每次盡可能地選取重量最小的物品最大裝載問(wèn)題最小生成樹(shù)樹(shù): 無(wú)回路的連通子圖生成樹(shù)：含圖中所有頂點(diǎn)的樹(shù)最小生成樹(shù): 加權(quán)圖中權(quán)值最小的生成樹(shù) 最小生成樹(shù)

5、最小生成樹(shù): 加權(quán)圖中權(quán)值最小的生成樹(shù) abcde1810282420161512abcde10242015abcde1810281210abcde182012窮舉法窮舉法: O(2n)最小生成樹(shù)Prim算法: 每次選取連接V和VV的權(quán)值最小的邊 abcde1810282420161512abcde18101512最小生成樹(shù)O(n2)Algorithm Prim(V: set; E: set; w: int,)begin let n = |V|, Y = E E0; let V = E0.a, E0.b, E = E0, tw = wE0; while (|V| n) do let i = 0

6、; while (i |Y|) do if (Yi.aV Yi.bV) (Yi.aV Yi.bV) break; i i + 1; let e = Yi; /e為V和VV之間的最小邊 E E e; V V e.a, e.b; tw tw + we; Y Y e; return (E, tw);endPrim算法: 每次選取連接V和VV的權(quán)值最小的邊 最小生成樹(shù)最優(yōu)性證明：1權(quán)值最小的邊e0可以包含在G的最小生成樹(shù)中。2設(shè)T = 為最小生成樹(shù)T的一棵子樹(shù)，e為連接V和VV之間的所有邊中權(quán)值最小的一條，那么e可以包含在最小生成樹(shù)中。 按數(shù)學(xué)歸納法，Prim算法的結(jié)果是一棵最小生成樹(shù)。Prim算法:

7、 每次選取連接V和VV的權(quán)值最小的邊 最小生成樹(shù)Kruskal算法: 每次選取不產(chǎn)生回路的最小邊 abcde1810282420161512abcde18101512最小生成樹(shù)Kruskal算法: 每次選取不產(chǎn)生回路的最小邊 O(m logm)Algorithm Kruskal(V: set; E: set; w: int,)begin let n = |V|, Y = E E0; let V = E0.a,E0.b, E = E0, tw = wE0; while (|V0| |V|) do for i = 0 to |Y|-1 do e = Yi; if (AddWithoutLoop(V

8、, e) then E E e; tw tw + we; Y Y e; break; return (E, tw);end最小生成樹(shù)最優(yōu)性證明：1權(quán)值最小的邊e0可以包含在G的最小生成樹(shù)中。2設(shè)T = 為最小生成樹(shù)T的一個(gè)無(wú)環(huán)子圖，e為EE中權(quán)值最小、且Ee不會(huì)產(chǎn)生回路的一條邊，那么e可以包含在最小生成樹(shù)中。 按數(shù)學(xué)歸納法，Kruskal算法的結(jié)果是一棵最小生成樹(shù)。Kruskal算法: 每次選取不產(chǎn)生回路的最小邊 最小生成樹(shù)破圈算法: 每次刪除現(xiàn)有回路中的最大邊 abcde1810282420161512abcde1810282420161512最小生成樹(shù)破圈算法: 每次刪除現(xiàn)有回路中的最大邊

9、 O(mn)Algorithm Guan(V: set; E: set; w: int,)begin let E = E; foreach (e E) do if (Connect(V, Ee, e.a, e.b) then E E e; return (V,E);end最小生成樹(shù)最優(yōu)性證明：每次“破圈時(shí)刪除的邊都不屬于最小生成樹(shù)。破圈算法: 每次刪除現(xiàn)有回路中的最大邊 單源最短路徑輸入: 連通圖G = (權(quán)值非負(fù))，s,tV輸出: 圖中從s到t的最短路徑單源最短路徑Dijkstra算法: 每次選取VV中距s最近的一個(gè)頂點(diǎn) abcde1810282420161512abcde18102815單

10、源最短路徑O(n2)Algorithm Dijkstra(V: set; E: set; w: int,; s: int)begin let n = |V|, V = s, X = Vs; let dis = new intn, pre = new intn; for i=0 to n-1 do disi ws,i; prei s; while (|V| 0) do let d = disv+wv,v; if (disv d) then disv d; prev v; return (dis, pre);endDijkstra算法: 每次選取VV中距s最近的一個(gè)頂點(diǎn)單源最短路徑最優(yōu)性證明：【定

11、理】在算法的每一步，對(duì)所選取的頂點(diǎn)vV，disv是圖中從s到v的最短距離。證明數(shù)學(xué)歸納法Dijkstra算法: 每次選取VV中距s最近的一個(gè)頂點(diǎn)貪心調(diào)度往返運(yùn)輸問(wèn)題輸入: 數(shù)組d，其中di為倉(cāng)庫(kù)到第i個(gè)客戶的距離 (0in)輸出: 輸送序列，使得客戶的等待時(shí)間之和iti最小s1s2s4ss313102016s58貪心調(diào)度往返運(yùn)輸問(wèn)題貪心策略: 優(yōu)先選取最近的尚未輸送的客戶s1s2s4ss313102016s58貪心調(diào)度帶權(quán)重的往返運(yùn)輸問(wèn)題輸入: 數(shù)組d和r，其中di為倉(cāng)庫(kù)到第i個(gè)客戶的距離，ri為第i個(gè)客戶的泉州 (0its0.b是ts中所有與0相容的活動(dòng)集，那么T0是S的最大相容子集。 按數(shù)學(xué)歸納法，貪心算法的結(jié)果是最大相容子集。區(qū)間活動(dòng)安排問(wèn)題貪心策略: 優(yōu)先選取最早結(jié)束的尚未安排的相容活動(dòng)貪心調(diào)度單位時(shí)間任務(wù)調(diào)