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

第7章每一步局部最優(yōu)—貪心法7.1貪心法概述7.2求解組合問題7.3求解圖問題7.4求解調(diào)度問題7.5哈夫曼編碼CONTENTS提綱1/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)度問題通常有兩種，一是不帶懲罰，另外一種是帶懲罰的。2/197.4.1不帶懲罰的調(diào)度問題不帶懲罰的調(diào)度問題的最優(yōu)解是最小系統(tǒng)總時(shí)間，實(shí)際上n個(gè)作業(yè)的加工順序不同對(duì)應(yīng)的系統(tǒng)總時(shí)間也不相同，該問題就是求一個(gè)具有最小系統(tǒng)總時(shí)間的加工順序。貪心策略是選擇當(dāng)前加工時(shí)間最小的作業(yè)優(yōu)先加工，也就是按加工時(shí)間遞增排序，再按排序后的順序依次加工。3/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=304/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)在排序上，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(nlog2n)。正確性證明：略。5/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í)間之后完成，對(duì)應(yīng)有一個(gè)懲罰值（punish）。該問題的最優(yōu)解是最小總懲罰值。6/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=507/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=08/198 foriinrange(0,n):9 j=a[i][0]10 whilej>0: #查找截止日期之前的空時(shí)間11 ifnotdays[j]:

#找到空時(shí)間12 days[j]=True13 print("作業(yè)[%d,%d]在第%d天完成"%(a[i][0],a[i][1],j))14 break15 j-=116 ifj==0: #沒有找到空時(shí)間17 ans+=a[i][1] #累計(jì)懲罰值18 print("不能完成作業(yè)[%d,%d],懲罰%d" %(a[i][0],a[i][1],a[i][1]))19 returnans【算法分析】上述算法有兩重循環(huán)，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(n2)。9/197.5哈夫曼編碼7.5.1哈夫曼樹和哈夫曼編碼問題描述：設(shè)需要編碼的字符集為{d0，d1，…，dn-1}，它們出現(xiàn)的頻率為{w0，w1，…，wn-1}，應(yīng)用哈夫曼樹構(gòu)造最優(yōu)的不等長(zhǎng)的由0、1構(gòu)成的編碼方案（哈夫曼編碼）。10/19構(gòu)造一棵哈夫曼樹由給定的n個(gè)權(quán)值{w0，w1，…，wn-1}構(gòu)造n棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合F={T0，T1，…，Tn-1}。在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和。即合并兩棵二叉樹為一棵二叉樹。重復(fù)步驟②，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。11/19利用哈夫曼樹構(gòu)造的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。哈夫曼樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定指向左子樹根的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是哈夫曼編碼。構(gòu)造哈夫曼編碼12/19證明算法的正確性，也就是證明如下兩個(gè)命題是成立的。命題7.4兩個(gè)最小權(quán)值字符對(duì)應(yīng)的結(jié)點(diǎn)x和y必須是哈夫曼樹中最深的兩個(gè)結(jié)點(diǎn)且它們互為兄弟。命題7.5設(shè)T是字符集C對(duì)應(yīng)的一棵哈夫曼樹，結(jié)點(diǎn)x和y是兄弟，它們的雙親為z，顯然有wz=wx+wy，現(xiàn)刪除結(jié)點(diǎn)x和y，讓z變?yōu)槿~子結(jié)點(diǎn)，那么這棵新樹T1一定是字符集C1=C-{x，y}∪{z}的最優(yōu)樹。13/19abcde71423(a)初始cb321(b)第1次合并cbe32136(c)第2次合并a4cbe3213610(d)第3次合并a4cbe3213610d717(e)第4次合并14/19哈夫曼編碼a:10b:1111c:1110d:0e:110WPL=(1+2)×4+3×3+4×2+7×1=3600001111a4cbe3213610d71715/19問題描述：有n（1≤n≤30）塊石頭，每塊石頭的重量都是正整數(shù)（重量為1～1000）。每一回合從中選出兩塊最重的石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為x和y，且x≥y。那么粉碎的可能結(jié)果如下：如果

x=y，那么兩塊石頭都會(huì)被完全粉碎。如果

x≠y，那么重量為y的石頭將會(huì)完全粉碎，而重量為x的石頭新重量為x-y。最后最多只會(huì)剩下一塊石頭，求此石頭的重量，如果沒有石頭剩下結(jié)果為0。7.5.2實(shí)戰(zhàn)—最后一塊石頭的重量（LeetCode1046）16/19選石頭的過程與構(gòu)造哈夫曼樹的過程類似，只是這里選的是兩塊最重的石頭。用優(yōu)先隊(duì)列（大根堆）求解，每次出隊(duì)兩塊最重的石頭x和y，然后將x-y進(jìn)隊(duì)，直到僅有一塊石頭為止。由于heapq默認(rèn)為小根堆，為此將進(jìn)隊(duì)的整數(shù)加上負(fù)號(hào)，在出隊(duì)時(shí)再加上負(fù)號(hào)進(jìn)行恢復(fù)，從而變?yōu)榇蟾?。?7/191 class

Solution:2

def

lastStoneWeight(self,

stones:

List[int])

->

int:3

maxpq=[]

#大根堆4

for

i

in

range(0,len(stones)):5

heapq.heappush(maxpq,-stones[i])

#所有石頭進(jìn)隊(duì)6

x,y=0,07

while

maxpq:8

x=-heapq.heappop(maxpq)9

if

not

max