《算法設計與分析基礎》（Python語言描述） 課件 第7章貪心法2

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

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

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

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

#所有石頭進隊6

x,y=0,07

while

maxpq:8

x=-heapq.heappop(maxpq)9

if

not

max