《算法设计与分析基础》（Python语言描述） 课件 第7章贪心法2

第7章每一步局部最优—贪心法7.1贪心法概述7.2求解组合问题7.3求解图问题7.4求解调度问题7.5哈夫曼编码CONTENTS提纲1/197.4求解调度问题调度问题有许多形式，这里专指这样形式的调度问题，n个作业要在一台机器上加工，每个作业的加工时间可能不同，这样有些作业就需要等待，全部作业完工的时间为等待时间和加工时间之和，称为系统总时间。该调度问题通常有两种，一是不带惩罚，另外一种是带惩罚的。2/197.4.1不带惩罚的调度问题不带惩罚的调度问题的最优解是最小系统总时间，实际上n个作业的加工顺序不同对应的系统总时间也不相同，该问题就是求一个具有最小系统总时间的加工顺序。贪心策略是选择当前加工时间最小的作业优先加工，也就是按加工时间递增排序，再按排序后的顺序依次加工。3/19序号i作业编号no加工时间ti等待时间wi总时间si00505113582248123321214序号i作业编号no加工时间ti等待时间wi总时间si032021132522459305914按加工时间递增排序系统总时间T=2+5+9+14=304/191 defgreedly(a): #贪心算法2 a.sort() #递增排序3 T,w=0,0 #当前系统总时间和当前作业的等待时间4 foriinrange(0,len(a)):#依次处理各个作业5 T+=a[i]+w6 w+=a[i]7 returnT【算法分析】算法的执行时间主要花费在排序上，对应的时间复杂度为O(nlog2n)。正确性证明：略。5/197.4.2带惩罚的调度问题带惩罚的调度问题中，通常假设n个作业加工时间均为一个时间单位，时间用0～maxd的连续整数表示，每个作业有一个截止时间（deadline用时间整数表示），当一个作业在其截止时间之后完成，对应有一个惩罚值（punish）。该问题的最优解是最小总惩罚值。6/19贪心策略：选择当前惩罚值最大的作业优先加工，按惩罚值递减排序，并且尽可能选择作业截止时间之前最晚的时间加工。按排序后的顺序依次加工。作业编号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("作业[%d,%d]在第%d天完成"%(a[i][0],a[i][1],j))14 break15 j-=116 ifj==0: #没有找到空时间17 ans+=a[i][1] #累计惩罚值18 print("不能完成作业[%d,%d],惩罚%d" %(a[i][0],a[i][1],a[i][1]))19 returnans【算法分析】上述算法有两重循环，对应的时间复杂度为O(n2)。9/197.5哈夫曼编码7.5.1哈夫曼树和哈夫曼编码问题描述：设需要编码的字符集为{d0，d1，…，dn-1}，它们出现的频率为{w0，w1，…，wn-1}，应用哈夫曼树构造最优的不等长的由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变为叶子结点，那么这棵新树T1一定是字符集C1=C-{x，y}∪{z}的最优树。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实战—最后一块石头的重量（LeetCode1046）16/19选石头的过程与构造哈夫曼树的过程类似，只是这里选的是两块最重的石头。用优先队列（大根堆）求解，每次出队两块最重的石头x和y，然后将x-y进队，直到仅有一块石头为止。由于heapq默认为小根堆，为此将进队的整数加上负号，在出队时再加上负号进行恢复，从而变为大根堆。解17/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