《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語言描述） 課件 第7章貪心法

第7章每一步局部最優(yōu)—貪心法7.1貪心法概述7.2求解組合問題7.3求解圖問題7.4求解調(diào)度問題7.5哈夫曼編碼CONTENTS提綱1/867.1.1什么是貪心法7.1貪心法概述每一步總是做出在當(dāng)前看來是最好的選擇，也就是說貪心法不從整體最優(yōu)上考慮，所做出的僅是在某種意義上的局部最優(yōu)解。解向量x=（x0，x1，…，xn-1）sn-1s0s1s2x0x1起始狀態(tài)…x2snxn-1目標(biāo)狀態(tài)2/86每一步的局部最優(yōu)選擇僅依賴以前的決策，且不依賴于以后的決策。所有局部最優(yōu)解合起來不一定構(gòu)成整體最優(yōu)解。所以貪心法不能保證對所有問題都得到整體最優(yōu)解。因此采用貪心法求最優(yōu)解時(shí)，必須證明該算法的每一步上做出的選擇都必然得到整體最優(yōu)解。3/867.1.2貪心法求解問題具有的性質(zhì)1.最優(yōu)子結(jié)構(gòu)性質(zhì)如果一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解，則稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。證明方法：采用反證法，先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后證明在這個(gè)假設(shè)下可以構(gòu)造出比原問題的最優(yōu)解更好的解，從而導(dǎo)致矛盾。4/862.貪心選擇性質(zhì)指整體最優(yōu)解可以通過一系列局部最優(yōu)選擇（即貪心選擇）來得到。證明方法：采用數(shù)學(xué)歸納法證明，即證明每一步所做的貪心選擇最終得到問題的整體最優(yōu)解。5/86問題描述：假設(shè)有n（1≤n≤30000）個(gè)孩子，現(xiàn)在給孩子們發(fā)一些小餅干，每個(gè)孩子最多只能給一塊餅干。每個(gè)孩子i有一個(gè)胃口值g[i]（1≤g[i]≤2^31-1），這是能滿足胃口的最小餅干尺寸，共有m塊餅干，每塊餅干j有一個(gè)尺寸s[j]。如果g[i]≤s[j]，那么將餅干j分發(fā)給孩子i時(shí)該孩子會(huì)得到滿足。

分發(fā)的目標(biāo)是盡可能滿足越多數(shù)量的孩子，設(shè)計(jì)一個(gè)算法求這個(gè)最大數(shù)值。

例如，g={1，2，3},s={1，1}，盡管有兩塊小餅干，由于尺寸都是1，只能讓胃口值是1的孩子滿足，所以結(jié)果是1。

要求設(shè)計(jì)如下方法： def

findContentChildren(self,

g,s)

->

int:7.1.3實(shí)戰(zhàn)—分發(fā)餅干（LeetCode455★）6/86解題目是求得到滿足的最多孩子數(shù)量，所以是一個(gè)求最優(yōu)解問題。很容易想到對于胃口為g[i]的孩子i，為其分發(fā)恰好滿足的最小尺寸的餅干j即min{j|g[i]≤s[j]}，不妨分發(fā)過程從最小胃口的孩子開始，為此將g遞增排序。對于每個(gè)s[i]，先在g查找剛好滿足g[i]≤s[j]的j，再將餅干j分發(fā)該孩子i。為了提高g中的查找性能，將s也遞增排序。7/86用ans表示得到滿足的最多孩子數(shù)量（初始為0）即最優(yōu)解，i從0開始遍歷g，j從0開始在s中查找：g[i]≤s[j]，說明為孩子i分發(fā)餅干j得到滿足，則將餅干j分發(fā)給孩子i，執(zhí)行ans++，同時(shí)執(zhí)行i++，j++繼續(xù)為下一個(gè)孩子分發(fā)合適的餅干。否則，孩子i得不到滿足，執(zhí)行j++繼續(xù)為其查找更大尺寸的餅干。最后的ans就是答案。8/86例如，g={3，1，5，3，8}，s={6，1，3，2}，排序后g={1，3，3，5，8}，s={1，2，3，6}，分發(fā)餅干的過程如下圖所示，結(jié)果ans=3。餅干s胃口g133581236ij找到最優(yōu)解9/861 class

Solution:2

def

findContentChildren(self,

g,s)

->

int:3

g.sort()

#默認(rèn)為遞增排序4

s.sort()5

ans=06

i,j=0,07

while

i<len(g)

and

j<len(s):8

if

g[i]<=s[j]:i,ans=i+1,ans+1 #i只有在滿足時(shí)增19

j+=1 #每次循環(huán)j增110

return

ans10/86如果將貪心選擇策略改為每個(gè)孩子i分發(fā)得到滿足的餅干j（不一定是最小尺寸的餅干），結(jié)果是否正確呢？11/867.1.4貪心法的一般求解過程①建立數(shù)學(xué)模型來描述問題。②把求解的問題分成若干個(gè)子問題。③對每一子問題求解，得到子問題的局部最優(yōu)解。④把子問題的解局部最優(yōu)解合成原問題的一個(gè)最優(yōu)解。12/861 defgreedy(a,n): #貪心算法框架2 x=[] #初始時(shí)，解向量為空3 foriinrange(0,n): #執(zhí)行n步操作4 xi=Select(a) #從輸入a中選擇一個(gè)當(dāng)前最好的分量5 ifFeasiable(xi): #判斷xi是否包含在當(dāng)前解中6 x=Union(xi) #將xi分量合并形成x7 returnx #返回生成的最優(yōu)解貪心法求解問題的算法框架13/86假設(shè)有n個(gè)活動(dòng)S=（1，2，…，n），有一個(gè)資源，每個(gè)活動(dòng)執(zhí)行時(shí)都要占用該資源，并且該資源任何時(shí)刻只能被一個(gè)活動(dòng)所占用，一旦某個(gè)活動(dòng)開始執(zhí)行，中間不能被打斷，直到其執(zhí)行完畢。每個(gè)活動(dòng)i有一個(gè)開始時(shí)間bi和結(jié)束時(shí)間ei（bi<ei），它是一個(gè)半開半閉時(shí)間區(qū)間[bi，ei），假設(shè)最早活動(dòng)執(zhí)行時(shí)間為0。求一種最優(yōu)活動(dòng)安排方案，使得安排的活動(dòng)個(gè)數(shù)最多。7.2.1活動(dòng)安排問題Ⅰ7.2求解組合問題14/86ejbj解biei(b)bi≥ejbj(a)bj≥eiejbiei對于兩個(gè)活動(dòng)i和j，若滿足bj≥ei或bi≥ej，則它們是不重疊的，稱為兩個(gè)兼容活動(dòng)。本問題就是在n個(gè)活動(dòng)中選擇最多的兼容活動(dòng)即求最多兼容活動(dòng)的個(gè)數(shù)。15/86用數(shù)組A存放所有的活動(dòng)，A[i].b（1≤i≤n）存放活動(dòng)起始時(shí)間，A[i].e存放活動(dòng)結(jié)束時(shí)間。貪心策略：每一步總是選擇執(zhí)行這樣的一個(gè)活動(dòng)，它能夠使得余下的活動(dòng)的時(shí)間最大化即余下活動(dòng)中兼容活動(dòng)盡可能多。為此先按活動(dòng)結(jié)束時(shí)間遞增排序，再從頭開始依次選擇兼容活動(dòng)（用B集合表示），從而得到最大兼容活動(dòng)子集即包含兼容活動(dòng)個(gè)數(shù)最多的子集。16/86i1234567891011開始時(shí)間b130535688212結(jié)束時(shí)間e4567891011121315求最大兼容活動(dòng)集B的過程i=1：preend=0，活動(dòng)1[1，4)的開始時(shí)間大于0，選擇它，preend=活動(dòng)1的結(jié)束時(shí)間=4，B={1}。i=2：活動(dòng)2[3，5)的開始時(shí)間小于preend，不選取。i=3：活動(dòng)3[0，6)的開始時(shí)間小于preend，不選取。i=4：活動(dòng)4[5，7)的開始時(shí)間大于preend，選擇它，preend=7，B={1，4}。i=5：活動(dòng)5[3，8)的開始時(shí)間小于preend，不選取。17/86i1234567891011開始時(shí)間b130535688212結(jié)束時(shí)間e4567891011121315i=6：活動(dòng)6[5，9)的開始時(shí)間小于preend，不選取。i=7：活動(dòng)7[6，10)的開始時(shí)間小于preend，不選取。i=8：活動(dòng)8[8，11)的開始時(shí)間大于preend，選擇它，preend=11，B={1，4，8}。i=9：活動(dòng)9[8，12)的開始時(shí)間小于preend，不選取。i=10：活動(dòng)10[2，13)的開始時(shí)間小于preend，不選取。i=11：活動(dòng)11[12，14)的開始時(shí)間大于preend，選擇它，preend=14，B={1，4，8，11}。18/8601234567891011112131415234567891011i1234567891011開始時(shí)間b130535688212結(jié)束時(shí)間e456789101112131519/861 classAction: #活動(dòng)類2 def__init__(self,b,e):3 self.b=b #活動(dòng)起始時(shí)間4 self.e=e #活動(dòng)結(jié)束時(shí)間5 def__lt__(self,other):

#用于按e遞增排序6 ifself.e<other.e:returnTrue7 else:returnFalse820/869 defgreedly(A): #貪心算法10 globalflag11 n=len(A)12 flag=[False]*n #初始化為False13 A.sort() #按e遞增排序14 preend=0; #前一個(gè)兼容活動(dòng)的結(jié)束時(shí)間15 foriinrange(0,n):16 ifA[i].b>=preend:17 flag[i]=True #選擇A[i]活動(dòng)18 preend=A[i].e1921/8620 defaction(A): #求解活動(dòng)安排問題Ⅰ22 greedly(A)23 print("求解結(jié)果");24 print("選取的活動(dòng):",end='')25 cnt=026 foriinrange(0,len(A)):27 ifflag[i]:28 print("[%d,%d]"%(A[i].b,A[i].e),end='')29 cnt+=130 print("\n共%d個(gè)活動(dòng)"%(cnt))22/86程序驗(yàn)證A=[Action(1,4),Action(3,5),Action(0,6),Action(5,7),\ Action(3,8),Action(5,9),Action(6,10),Action(8,11),\ Action(8,12),Action(2,13),Action(12,15)]action(A)23/86算法的主要時(shí)間花費(fèi)在排序上，排序時(shí)間為O(nlog2n)。所以整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。算法分析24/86算法證明所有活動(dòng)按結(jié)束時(shí)間遞增排序，這里就是要證明若X是A的最優(yōu)解，X=X'∪{1}，則X'是A'={i∈A：ei≥b1}的最優(yōu)解。那么A是不是總存在一個(gè)以活動(dòng)1開始的最優(yōu)解。如果第一個(gè)選擇的活動(dòng)為k（k≠1），可以構(gòu)造另一個(gè)最優(yōu)解Y，Y與X的活動(dòng)數(shù)相同。那么在Y中用活動(dòng)1取代活動(dòng)k得到Y(jié)'，因?yàn)閑1≤ek，所以Y'中活動(dòng)也是兼容的，即Y'也是最優(yōu)解，這就說明A總存在一個(gè)以活動(dòng)1開始的最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)25/86當(dāng)選擇活動(dòng)1后，原問題就變成了在A'中找兼容活動(dòng)的子問題。如果X為原問題的一個(gè)最優(yōu)解，而X'=X-{1}不是A'的一個(gè)最優(yōu)解，說明A'能夠找到的一個(gè)更優(yōu)解Y'，Y'中的兼容活動(dòng)個(gè)數(shù)多于X'，這樣將活動(dòng)1加入Y'后就得到A的一個(gè)更有解Y，Y中兼容活動(dòng)個(gè)數(shù)多于X，這就與X是最優(yōu)解的假設(shè)相矛盾。26/86貪心選擇性質(zhì)從前面最優(yōu)子結(jié)構(gòu)性質(zhì)證明可以看出，每一步所做的貪心選擇都將問題簡化為一個(gè)更小的與原問題具有相同形式的子問題，可以對貪心選擇次數(shù)用數(shù)學(xué)歸納法證明，這里不再詳述。27/86問題描述：給定一個(gè)含n個(gè)區(qū)間的集合intervals，每個(gè)區(qū)間的終點(diǎn)總是大于它的起點(diǎn)，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊，如區(qū)間{1，2}和{2，3}的邊界相互接觸，但沒有相互重疊。

例如，intervals={{1，2}，{2，3}，{3，4}，{1，3}}，移除區(qū)間{1，3}后剩下的區(qū)間沒有重疊，所以答案為1。

要求設(shè)計(jì)如下方法：def

eraseOverlapIntervals(self,intervals):7.2.2實(shí)戰(zhàn)—無重疊區(qū)間（LeetCode435★★）28/86解法1兩個(gè)相互不相交的區(qū)間就是兼容區(qū)間，采用前面活動(dòng)安排問題Ⅰ的貪心方法求出intervals中最多兼容區(qū)間的個(gè)數(shù)ans，那么n-ans就是使剩余區(qū)間互不重疊需要移除區(qū)間的最小數(shù)量。稍有不同的是這里的區(qū)間起點(diǎn)和終點(diǎn)可能為負(fù)數(shù)，所以表示終點(diǎn)的preend初始值應(yīng)該設(shè)置為-∞而不是0。29/861 class

Solution:2

def

eraseOverlapIntervals(self,intervals):3

INF=0x3f3f3f3f

#表示∞4

n=len(intervals)5

if

n<=1:return

06

intervals.sort(key=itemgetter(1))

#按區(qū)間終點(diǎn)遞增排序7

ans=0

#表示兼容區(qū)間的個(gè)數(shù)8

preend=-INF #初始化為-∞9

for

i

in

range(0,n):10

if

intervals[i][0]>=preend:11

ans+=1 #兼容區(qū)間的個(gè)數(shù)增112

preend=intervals[i][1]13

return

n-ans30/86解法2同樣兩個(gè)相互不相交的區(qū)間就是保留的區(qū)間，為了使保留的區(qū)間最多，每次選擇的區(qū)間結(jié)尾越小，留給其他區(qū)間的空間就越大，就越能保留更多的區(qū)間，這樣采用的貪心選擇策略是優(yōu)先保留結(jié)尾小且不相交的區(qū)間。為此先將intervals按區(qū)間終點(diǎn)遞增排序，ans表示最少相交區(qū)間的個(gè)數(shù)（初始為0），每次選擇結(jié)尾最小且和前一個(gè)選擇的區(qū)間不相交的區(qū)間，一旦找不到這樣的區(qū)間時(shí)ans增1，最后返回ans。31/861 class

Solution:2

def

eraseOverlapIntervals(self,intervals)->int:3

INF=0x3f3f3f3f

#表示∞4

n=len(intervals)5

if

n<=1:return

06

intervals.sort(key=itemgetter(1))

#按區(qū)間終點(diǎn)遞增排序7

ans=0

#表示兼容區(qū)間的個(gè)數(shù)8

preend=-INF #初始化為-∞9

for

i

in

range(0,n):10

if

intervals[i][0]<preend:

#找到一個(gè)相交區(qū)間11

ans+=1 #移除該區(qū)間12

else:13

preend=intervals[i][1]

#重置preend14

return

ans32/86解法1：通過，執(zhí)行用時(shí)為168ms，內(nèi)存消耗為44.9MB。解法2：通過，執(zhí)行用時(shí)為176ms，內(nèi)存消耗為44.8MB。33/86有n個(gè)編號(hào)為0～n-1的物品，重量為w={w0，w1，…，wn-1}，價(jià)值為v={v0，v1，…，vn-1}，給定一個(gè)容量為W的背包。從這些物品中選取全部或者部分物品裝入該背包中，找到選中物品不僅能夠放到背包中而且價(jià)值最大的方案。與0/1背包問題的區(qū)別是這里的每個(gè)物品可以取一部分裝入背包。物品編號(hào)no01234w1020304050v2030664060W=1007.2.3求解背包問題34/86貪心策略：每次選擇單位重量價(jià)值最大的物品。序號(hào)i01234物品編號(hào)no31254w3010205040v6620306040v/w2.22.01.51.21.0x[0]=1bestv=66rw=rw-w[0]=70x[1]=1bestv=66+20=86rw=rw-w[1]=60x[2]=1bestv=86+30=116rw=rw-w[2]=40x[3]=0.8bestv=116+0.8*60=16435/861 defgreedly(g,W): #貪心算法2 globalx,bestv3 n=len(g)4 g.sort() #按v/w遞減排序5 x=[0]*n #存放最優(yōu)解向量6 bestv=0 #存放最大價(jià)值,初始為07 rw=W #背包中能裝入的余下重量36/868 i=09 whilei<nandg[i].w<rw: #物品i能夠全部裝入時(shí)循環(huán)10 x[i]=1 #裝入物品i11 rw-=g[i].w #減少背包中能裝入的余下重量12 bestv+=g[i].v #累計(jì)總價(jià)值13 i+=1 #繼續(xù)循環(huán)14 ifi<nandrw>0: #當(dāng)余下重量大于015 x[i]=rw/g[i].w #將物品i的一部分裝入16 bestv+=x[i]*g[i].v #累計(jì)總價(jià)值1737/8618 defknap(g,W): #求解背包問題19 greedly(g,W)20 print("求解結(jié)果") #輸出結(jié)果21 forjinrange(0,len(g)):22 ifx[j]==1:print("選擇%d[%d,%d]物品的比例是1" %(g[j].no,g[j].w,g[j].v))23 elifx[j]>0:print("選擇%d[%d,%d]物品的比例是%.1f" %(g[j].no,g[j].w,g[j].v,x[j]))24 print("總價(jià)值=%d"%(bestv))38/86程序驗(yàn)證物品編號(hào)no01234w1020304050v203066406039/86排序算法sort()的時(shí)間復(fù)雜性為O(nlog2n)，while循環(huán)的時(shí)間為O(n)。所以算法的時(shí)間復(fù)雜度為O(nlog2n)。算法分析40/867.2.4實(shí)戰(zhàn)—雪糕的最大數(shù)量（LeetCode1833★★）問題描述：商店中新到n支雪糕，用數(shù)組costs表示雪糕的價(jià)格，Tony一共有coins的現(xiàn)金，他想要買盡可能多的雪糕。

設(shè)計(jì)一個(gè)算法求Tony用coins現(xiàn)金能夠買到的雪糕的最大數(shù)量，可以按任意順序購買雪糕。

例如，costs={1，3，2，4，1}，coins=7，可以買下標(biāo)為0、1、2、4的雪糕，總價(jià)為1+3+2+1=7，答案為4。

要求設(shè)計(jì)如下方法：public

int

maxIceCream(int[]

costs,

int

coins)

{}41/86解類似背包問題，采用的貪心策略是優(yōu)先選擇價(jià)格小的雪糕，這樣使得剩余金額盡可能的多，將來能夠做的決策方案也就相應(yīng)變多。為此先將costs遞增排序，然后從前向后處理，能夠買的雪糕則買下。42/861 class

Solution:2

def

maxIceCream(self,

costs,

coins)

->

int:3

costs.sort()

#默認(rèn)遞增排序4

ans=05

rc=coins

#剩余的金額（從coins開始）6

for

i

in

range(0,len(costs)):7

if

costs[i]<=rc:

#可以買則買該雪糕8

ans+=19

rc-=costs[i]10

return

ans43/86問題描述：給定一組非負(fù)整數(shù)nums，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)最大的整數(shù)。由于輸出結(jié)果可能非常大，所以需要返回一個(gè)字符串而不是整數(shù)。

例如，nums={3，30，34，5，9}，輸出結(jié)果為"9534330"。

7.2.5實(shí)戰(zhàn)—最大數(shù)（LeetCode179★★）44/86解采用的貪心策略是將數(shù)字位越大的數(shù)字越排在前面，然后從前向后進(jìn)行合并即可。那么是不是直接將整數(shù)序列nums遞減排序后再從前向后合并呢？答案是錯(cuò)誤的，例如nums=（50，2，1，9）遞減排序后為（50，9，2，1），合并后的結(jié)果是"50921"而不是正確的"95021"。為此改為這樣的排序方式，對于兩個(gè)整數(shù)a和b，將它們轉(zhuǎn)換為字符串s和t，若s+t>t+s，則a排在b的前面，例如，對于50和9兩個(gè)整數(shù)，轉(zhuǎn)換為字符串"50"和"9"，由于"950">"509"，所以"9">"50"。按照這種方式排序后，依次合并起來得到字符串a(chǎn)ns。如果ans的首字符為'0'，說明后面的元素均為0，則可直接返回"0"。45/861 import

functools2 class

Solution:3

def

largestNumber(self,

nums:

List[int])

->

str:4

a=[]5

for

x

in

nums:

#將nums轉(zhuǎn)換為字符串?dāng)?shù)組a6

a.append(str(x))7

def

cmp(s,t):

#按指定方式排序8

if

s+t<t+s:return

19

else:return

-146/8610

a.sort(key=functools.cmp_to_key(cmp))11

ans=""12

for

i

in

range(len(a)):ans+=a[i]

#依次合并得到ans13

if

ans[0]=='0':return

"0"

#處理特殊情況14

else:return

ans47/86問題描述：有面額分別是c0、c1、…、ck（c≥2，k為非負(fù)整數(shù)）的k+1種硬幣，每種硬幣個(gè)數(shù)可以看成無限多，求兌換A金額的最少硬幣個(gè)數(shù)。7.2.6求解零錢兌換問題48/86解

采用貪心法，貪心策略是盡可能選擇面額大的硬幣進(jìn)行兌換，例如，c=2，k=3，面額分別是{1，2，4，8}，A=23的兌換過程如下：選擇面額為8的硬幣，兌換的硬幣個(gè)數(shù)=A/8=2，剩余金額=23-2×8=7。選擇面額為4的硬幣，兌換的硬幣個(gè)數(shù)=A/4=1，剩余金額=7-4×1=3。選擇面額為2的硬幣，兌換的硬幣個(gè)數(shù)=A/2=1，剩余金額=3-2×1=1。選擇面額為1的硬幣，兌換的硬幣個(gè)數(shù)=A/1=1，剩余金額=1-1×1=0。總硬幣個(gè)數(shù)=2+1+1+1=549/861 defgreedly(c,k,A): #貪心算法2 ans=03 curm=2**k4 whileA>0:5 curs=A//curm #求面額為curm的硬幣個(gè)數(shù)6 ans+=curs #累計(jì)硬幣個(gè)數(shù)7 print("面額為%d的硬幣個(gè)數(shù)=%d"%(curm,curs))8 A-=curs*curm #剩余金額9 curm/=c;10 returnans1112 defsolve(c,k,A): #求解零錢兌換問題13 print("求解結(jié)果")14 print("兌換金額%d的最少硬幣個(gè)數(shù)=%d"%(A,greedly(c,k,A)))50/86A=23c=2k=3solve(c,k,A)程序驗(yàn)證51/867.3.1Prim算法構(gòu)造最小生成樹7.3求解圖問題Prim（普里姆）算法是一種構(gòu)造性算法。假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通圖，T=（U，TE）是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，由G構(gòu)造從起始頂點(diǎn)v出發(fā)的最小生成樹T。52/86386174265054126338617426505412633861742650541263386174265054126353/86386174265054126338617426505412633861742650541263③3⑥6①1④4⑤2②60541263一棵最小生成樹54/86U={i|U[i]=1}V-U={j|U[j]=0}lowcost[j]closest[j]vkj算法中的符號(hào)：55/861 INF=0x3f3f3f3f2 defPrim(A,n,v): #Prim算法3 T=[] #存放最小生成樹4 lowcost=[INF]*n5 U=[0]*n6 closest=[0]*n7 forjinrange(0,n): #初始化lowcost和closest數(shù)組8 lowcost[j]=A[v][j]9 closest[j]=v10 U[v]=1 #源點(diǎn)加入U(xiǎn)56/8611 foriinrange(1,n): #找出(n-1)個(gè)頂點(diǎn)12 mincost,k=INF,-113 forjinrange(0,n): #在(V-U)中找離U最近的頂點(diǎn)k14 ifU[j]==0andlowcost[j]<mincost:15 mincost=lowcost[j]16 k=j #k記錄最近頂點(diǎn)的編號(hào)17 T.append([closest[k],k,mincost]) #產(chǎn)生最小生成樹的一條邊18 U[k]=1 #頂點(diǎn)k加入U(xiǎn)19 forjinrange(0,n): #修改數(shù)組lowcost和closest20 ifU[j]==0andA[k][j]<lowcost[j]:21 lowcost[j]=A[k][j]22 closest[j]=k23 returnT【算法分析】Prim()算法中有兩重for循環(huán)，所以時(shí)間復(fù)雜度為O(n2)。57/86Prim算法是一種貪心算法，如何理解Prim算法的最優(yōu)子結(jié)構(gòu)性質(zhì)呢？10332210312(a)一個(gè)帶權(quán)連通圖32210312(b)子問題58/86采用反證法證明Prim算法滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。證明：如果采用Prim算法求出原問題的生成樹T是最小生成樹，選擇第一條邊(v，a)后得到相應(yīng)的子問題，假設(shè)該子問題采用Prim算法求出的生成樹T1（T=(v，a)∪T1）不是最小的，而是最小生成樹為T2，則(v，a)∪T2得到原問題的一棵不同于T的更小的最小生成樹，用T是原問題的最小生成樹矛盾。最優(yōu)子結(jié)構(gòu)性質(zhì)即證。32210312(b)子問題59/86貪心選擇性質(zhì)證明。證明：k=1時(shí)，由前面最優(yōu)子結(jié)構(gòu)性質(zhì)證明可以得出命題是成立的。命題7.1對于任意正整數(shù)k<n，存在一棵最小生成樹T包含Prim算法前k步選擇的邊。60/86ek=(il，ik)e'UV-Uilikxy假設(shè)算法進(jìn)行了k-1步，生成樹的邊為e1，e2，…，ek-1，這些邊的k個(gè)頂點(diǎn)構(gòu)成集合U，并且存在G的一棵最小生成樹T包含這些邊。算法第k步選擇了頂點(diǎn)ik，則ik到U中頂點(diǎn)的邊的權(quán)值最小，設(shè)這條邊為ek=(il，ik)。假設(shè)最小生成樹T不含有邊ek，將ek添加到T中形成一個(gè)回路，如下圖所示，這個(gè)回路一定有連接U與V-U中頂點(diǎn)的邊e'，用ek替換e'得到樹T'，即T'=(T-{e'})∪{ek}。61/86則T'也是一棵生成樹，包含邊e1，e2，…，ek-1，ek，并且T'所有邊權(quán)值和更?。ǔ莈'與ek的權(quán)相同），與T為一棵最小生成樹矛盾，命題7.1即證。ek=(il，ik)e'UV-Uilikxy62/86當(dāng)命題7.1成立時(shí)，k=n-1即選擇了n-1條邊，此時(shí)U包含G中所有頂點(diǎn)，由Prim算法構(gòu)造的T=（U，TE）就是G的最小生成樹。命題7.1對于任意正整數(shù)k<n，存在一棵最小生成樹T包含Prim算法前k步選擇的邊。63/867.3.2Kruskal算法構(gòu)造最小生成樹Kruskal（克魯斯卡爾）算法按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹。假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)e條邊的帶權(quán)連通無向圖，T=(U，TE)是G的最小生成樹。64/863861742650541263(a)一個(gè)帶權(quán)連通圖38617426505412633861742650541263386174265054126365/86386174265054126338617426505412633861742650541263③3⑥6①1④4②2⑤60541263一棵最小生成樹66/86首先，U中包含全部頂點(diǎn)，TE為空，看成是由n個(gè)連通分量構(gòu)成的圖，每個(gè)連通分量中只有一個(gè)頂點(diǎn)，當(dāng)考慮一條邊(u，v)時(shí)，若u和v屬于兩個(gè)不同的連通分量，則加入該邊不會(huì)出現(xiàn)回路，否則會(huì)出現(xiàn)回路。這里每個(gè)連通分量就是并查集中的子集樹。用數(shù)組E存放圖G中的所有邊，按權(quán)值遞增排序，再從頭到尾依次考慮每一條邊，若可以加入則選擇該邊作為最小生成樹的一條邊，否則舍棄該邊。67/86#UFS并查集類參見第2章2.10.2節(jié)1～23的代碼1 INF=0x3f3f3f3f2 defKruskal(A,n): #Kruskal算法3 T=[] #存放最小生成樹4 E=[] #邊集5 foriinrange(0,n): #由A下三角部分產(chǎn)生的邊集E6 forjinrange(0,i):7 ifA[i][j]!=0andA[i][j]!=INF:8 E.append([i,j,A[i][j]])9 E.sort(key=itemgetter(2)) #按邊權(quán)值遞增排序10 ufs=UFS()

#定義并查集對象11 ufs.Init(n)

#初始化并查集12 k,j=0,0 #k表示當(dāng)前構(gòu)造生成樹的邊數(shù)68/8613 whilek<n-1: #生成的邊數(shù)小于n-1時(shí)循環(huán)14 u1,v1=E[j][0],E[j][1] #取一條邊(u1,v1)15 sn1,sn2=ufs.Find(u1),ufs.Find(v1) #兩個(gè)頂點(diǎn)所屬的集合編號(hào)16 ifsn1!=sn2: #添加該邊不會(huì)構(gòu)成回路17 T.append([u1,v1,E[j][2]]) #產(chǎn)生最小生成樹的一條邊18 k+=1 #生成邊數(shù)增119 ufs.Union(sn1,sn2) #將sn1和sn2兩個(gè)頂點(diǎn)合并20 j+=1 #遍歷下一條邊21 returnT69/86【算法分析】排序時(shí)間為O(elog2e)，while循環(huán)是在e條邊中選取n-1條邊，最壞情況下執(zhí)行e次，Union的執(zhí)行時(shí)間為O(log2n)，所以上述Kruskal算法構(gòu)造最小生成樹的時(shí)間復(fù)雜度為O(elog2e)?！綤ruskal算法的正確性證明】和Prim算法一樣都是貪心算法，其正確性證明與Prim算法類似，這里不再詳述。70/86問題描述：給定一個(gè)points數(shù)組，表示二維平面上的一些點(diǎn)，其中

points[i]={xi，yi}。連接兩個(gè)點(diǎn){xi，yi}和{xj，yj}的費(fèi)用為它們之間的曼哈頓距離即|xi-xj|+|yi-yj|。

求將所有點(diǎn)連接的最小總費(fèi)用，只有任意兩點(diǎn)之間有且僅有一條簡單路徑時(shí)才認(rèn)為所有點(diǎn)都已連接。

例如，points={{0，0}，{2，2}，{3，10}，{5，2}，{7，0}}，答案為20。

7.3.3實(shí)戰(zhàn)—連接所有點(diǎn)的最小費(fèi)用（LeetCode1584★★）71/86解法1：Prim算法本題給定的n個(gè)點(diǎn)看成是一個(gè)完全無向圖，邊的權(quán)值為對應(yīng)兩個(gè)點(diǎn)的曼哈頓距離，問題轉(zhuǎn)化為求最小生成樹的長度（最小生成樹中所有邊的權(quán)值和）。解法2：Kruskal算法Prim：執(zhí)行用時(shí)為704ms，內(nèi)存消耗為15.3MB。Kruskal：執(zhí)行用時(shí)為1172ms，內(nèi)存消耗為96.9MB。？60%和15.8%72/867.3.4Dijkstra算法求單源最短路徑設(shè)G=(V，E)是一個(gè)帶權(quán)有向圖，所有邊的權(quán)值為正數(shù)，給定一個(gè)源點(diǎn)v，求v到圖中其他頂點(diǎn)的最短路徑長度。Dijkstra（狄克斯特拉）算法把圖中頂點(diǎn)集合V分成兩組，第1組為已求出最短路徑的頂點(diǎn)集合（用S表示），初始時(shí)S中只有一個(gè)源點(diǎn)v，第2組為其余未求出最短路徑的頂點(diǎn)集合（用U表示）。每求得一條最短路徑v，…，u，就將u加入到集合S中（重復(fù)n-1次），直到全部頂點(diǎn)都加入到S中。73/86在向S中添加頂點(diǎn)u時(shí)，對于U中的每個(gè)頂點(diǎn)j，如果頂點(diǎn)u到頂點(diǎn)j有邊（權(quán)值為wuj），且原來從頂點(diǎn)v到頂點(diǎn)j的路徑長度（Dvj）大于從頂點(diǎn)v到頂點(diǎn)u的路徑長度（Dvu）與wuj之和，Dvj>Dvu+wuj，則將v

…

u→j的路徑作為v到j(luò)的新最短路徑，即Dvj=min(Dvj，Dvu+wuj)。vjuDvuwujDvj有一條邊有一條路徑Dvj=min(Dvj，cvu+wuj)74/86vjuA[u][j]松馳操作：dist[j]=min(dist[j],dist[u]+A[u][j])dist[u]dist[j]帶權(quán)有向圖用鄰接矩陣A表示dist[i]表示從源點(diǎn)v到頂點(diǎn)i的目前最短路徑長度75/861 defDijkstra(A,n,v): #Dijkstra算法2 globaldist3 dist=[0]*n4 S=[False]*n5 foriinrange(0,n):6 dist[i]=A[v][i] #距離初始化7 S[v]=True #源點(diǎn)v放入S中76/868 foriinrange(0,n-1): #循環(huán)n-1次9 u,mindis=-1,INF10 forjinrange(0,n): #選取U中具有最小距離的頂點(diǎn)u11 ifnotS[j]anddist[j]<mindis:12 u=j13 mindis=dist[j]14 ifu==-1:break15 S[u]=True #頂點(diǎn)u加入S中16 forjinrange(0,n): #修改U中的頂點(diǎn)的距離17 ifnotS[j]andA[u][j]!=0andA[u][j]<INF:18 dist[j]=min(dist[j],dist[u]+A[u][j])【算法分析】Dijkstra()算法中時(shí)間復(fù)雜度為O(n2)77/86Dijkstra算法的正確性證明轉(zhuǎn)換為證明以下命題成立。命題7.2Dijkstra算法中當(dāng)頂點(diǎn)u添加的S中時(shí)，dist[u]等于從源點(diǎn)v到u的最短路徑長度D[v，u]（D[i，j]表示圖中從頂點(diǎn)i到j(luò)的真實(shí)最短路徑長度）。證明：假設(shè)對于V中的某個(gè)頂點(diǎn)t，dist[t]>D[v,t]，并設(shè)u是算法中添加到S中的第一個(gè)滿足dist[u]>D[v,u]的頂點(diǎn)。因?yàn)榇嬖趶脑袋c(diǎn)v到u的最短路徑P，考慮當(dāng)u添加到S的時(shí)刻，令z是此時(shí)不在S中的P路徑上的第一個(gè)頂點(diǎn)。令y是路徑P中z的前一個(gè)頂點(diǎn)（可能有y=v）。78/86dist[u]>D[v,u]dist[z]=D[v,z]vuzPSyu是下一個(gè)選擇，因此dist[u]≤dist[z]第一個(gè)“不正確”的頂點(diǎn)dist[y]=D[v,y]現(xiàn)在選擇的是將u添加的S中而不是z，因此有dist[u]≤dist[z]（按照Dijkstra算法，越先添加到S中其dist越?。?。顯然任何一條最短路徑的子路徑也是最短路徑，因此，由于z在從v到u的最短路徑上，則有D[v，z]+D[z,u]=D[v,u]。此外，D[z,u]≥0（因?yàn)閳D中沒有負(fù)權(quán)），因此：dist[u]≤dist[z]=D[v,s]≤D[v,z]+D[z,u]=D[v,u]這樣與u的定義矛盾。因此這樣的頂點(diǎn)u不存在。命題7.2即證。79/86問題描述：有n個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)，標(biāo)記為1到n。給定一個(gè)列表times，表示信號(hào)經(jīng)過有向邊的傳遞時(shí)間，times[i]=（ui，vi，wi），其中ui是源結(jié)點(diǎn)，vi是目標(biāo)結(jié)點(diǎn)，wi是一個(gè)信號(hào)從源結(jié)點(diǎn)傳遞到目標(biāo)結(jié)點(diǎn)的時(shí)間。

現(xiàn)在從某個(gè)結(jié)點(diǎn)k（1≤k≤n）發(fā)出一個(gè)信號(hào)，設(shè)計(jì)一個(gè)算法求需要多久才能使所有結(jié)點(diǎn)都收到信號(hào)？如果不能使所有結(jié)點(diǎn)收到信號(hào)，返回-1

。

例如，times={{2，1，1}，{2，3，1}，{3，4，1}}，n=4，k=2，結(jié)果為2。

7.3.5實(shí)戰(zhàn)—網(wǎng)絡(luò)延遲時(shí)間（LeetCode743★★）80/86用鄰接表adj存放帶權(quán)有向圖，先由邊數(shù)組times創(chuàng)建adj（注意頂點(diǎn)編號(hào)從1～n改為0～n-1），采用Dijkstra算法的過程求出dist數(shù)組。解012531adj=[[[1,1],[2,3]], #adj[0][[2,5]], #adj[1][[]] #adj[2]]81/86用鄰接表adj存放帶權(quán)有向圖，先由邊數(shù)組times創(chuàng)建adj（注意頂點(diǎn)編號(hào)從1～n改為0～n-1），采用Dijkstra算法的過程求出dist數(shù)組。再在dist數(shù)組中求最大值ans，若ans=INF說明不能使所有結(jié)點(diǎn)收到信號(hào)，返回-1，否則返回ans。82/861 class

Solution:2

INF=0x3f3f3f3f3

def

networkDelayTime(self,

times,

n,

k)

->

int:4

adj=[[]

for

i

in

range(n)]

#圖的鄰接表5

for

x

in

times:

#遍歷times建立鄰接表6

adj[x[0]-1].append([x[1]-1,x[2]])7

dist=self.Dijkstra(adj,n,k-1)8

ans=dist[0]9

for

i

in

range(1,n):10

ans=max(ans,dist[i])11

if

ans==self.INF:return

-112

else:return

ans1383/8614

def

Dijkstra(self,adj,n,v):

#基于優(yōu)先隊(duì)列的Dijkstra算法15

dist=[self.INF]*n16

S=[False]*n17

minpq=[]

#定義一個(gè)小根堆18

dist[v]=019

heapq.heappush(minpq,[dist[v],v])84/8620

while

minpq:21

x=heapq.heappop(minpq)

#出隊(duì)結(jié)點(diǎn)e22

u=x[1]23

S[u]=True24

for

e

in

adj[u]:25

v,w=e[0],e[1]26

if

not

S[v]

and

dist[u]+w<dist[v]:27

dist[v]=dist[u]+w28

heapq.heappush(minpq,[dist[v],v])29

return

distuvwdist[u]dist[v]源85/86上述程序提交時(shí)通過，執(zhí)行時(shí)間為80ms，內(nèi)存消耗為16.9MB。86/86第7章每一步局部最優(yōu)—貪心法7.1貪心法概述7.2求解組合問題7.3求解圖問題7.4求解調(diào)度問題7.5哈夫曼編碼CONTENTS提綱87/197.4求解調(diào)度問題調(diào)度問題有許多形式，這里專指這樣形式的調(diào)度問題，n個(gè)作業(yè)要在一臺(tái)機(jī)器上加工，每個(gè)作業(yè)的加工時(shí)間可能不同，這樣有些作業(yè)就需要等待，全部作業(yè)完工的時(shí)間為等待時(shí)間和加工時(shí)間之和，稱為系統(tǒng)總時(shí)間。該調(diào)度問題通常有兩種，一是不帶懲罰，另外一種是帶懲罰的。88/197.4.1不帶懲罰的調(diào)度問題不帶懲罰的調(diào)度問題的最優(yōu)解是最小系統(tǒng)總時(shí)間，實(shí)際上n個(gè)作業(yè)的加工順序不同對應(yīng)的系統(tǒng)總時(shí)間也不相同，該問題就是求一個(gè)具有最小系統(tǒng)總時(shí)間的加工順序。貪心策略是選擇當(dāng)前加工時(shí)間最小的作業(yè)優(yōu)先加工，也就是按加工時(shí)間遞增排序，再按排序后的順序依次加工。89/19序號(hào)i作業(yè)編號(hào)no加工時(shí)間ti等待時(shí)間wi總時(shí)間si00505113582248123321214序號(hào)i作業(yè)編號(hào)no加工時(shí)間ti等待時(shí)間wi總時(shí)間si032021132522459305914按加工時(shí)間遞增排序系統(tǒng)總時(shí)間T=2+5+9+14=3090/191 defgreedly(a): #貪心算法2 a.sort() #遞增排序3 T,w=0,0 #當(dāng)前系統(tǒng)總時(shí)間和當(dāng)前作業(yè)的等待時(shí)間4 foriinrange(0,len(a)):#依次處理各個(gè)作業(yè)5 T+=a[i]+w6 w+=a[i]7 returnT【算法分析】算法的執(zhí)行時(shí)間主要花費(fèi)在排序上，對應(yīng)的時(shí)間復(fù)雜度為O(nlog2n)。正確性證明：略。91/197.4.2帶懲罰的調(diào)度問題帶懲罰的調(diào)度問題中，通常假設(shè)n個(gè)作業(yè)加工時(shí)間均為一個(gè)時(shí)間單位，時(shí)間用0～maxd的連續(xù)整數(shù)表示，每個(gè)作業(yè)有一個(gè)截止時(shí)間（deadline用時(shí)間整數(shù)表示），當(dāng)一個(gè)作業(yè)在其截止時(shí)間之后完成，對應(yīng)有一個(gè)懲罰值（punish）。該問題的最優(yōu)解是最小總懲罰值。92/19貪心策略：選擇當(dāng)前懲罰值最大的作業(yè)優(yōu)先加工，按懲罰值遞減排序，并且盡可能選擇作業(yè)截止時(shí)間之前最晚的時(shí)間加工。按排序后的順序依次加工。作業(yè)編號(hào)no截止時(shí)間di懲罰值pi0470126024503340413054206610days[i]表示時(shí)間i是否在加工,初始均為F選時(shí)間4，days[4]=T，不懲罰，ans=0選時(shí)間2，days[2]=T，不懲罰，ans=0選時(shí)間3，days[3]=T，不懲罰，ans=0選時(shí)間1，days[1]=T，不懲罰，ans=0時(shí)間1已占，不能加工，懲罰，ans=30時(shí)間1～4已占，不能加工，懲罰，ans=30+20=50選時(shí)間6，days[6]=T，不懲罰

ans=5093/191 defgreedly(a): #貪心算法2 n=len(a)3 maxd=04 foriinrange(0,n):maxd=max(maxd,a[i][0])5 days=[False]*(maxd+1)6 a.sort(key=itemgetter(1),reverse=True)#按懲罰值遞減排序7 ans=094/198 foriinrange(0,n):9 j=a[i][0]10 while