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

第7章每一步局部最优—贪心法;7.4求解调度问题;7.4.1不带惩罚的调度问题;序号i;1 defgreedly(a): #贪心算法

2 a.sort() #递增排序

3 T,w=0,0 #当前系统总时间和当前作业的等待时间

4 foriinrange(0,len(a)):#依次处理各个作业

5 T+=a[i]+w

6 w+=a[i]

7 returnT;7.4.2带惩罚的调度问题;贪心策略：选择当前惩罚值最大的作业优先加工，按惩罚值递减排序，并且尽可能选择作业截止时间之前最晚的时间加工。按排序后的顺序依次加工。;1 defgreedly(a): #贪心算法

2 n=len(a)

3 maxd=0

4 foriinrange(0,n):maxd=max(maxd,a[i][0])

5 days=[False]*(maxd+1)

6 a.sort(key=itemgetter(1),reverse=True)#按惩罚值递减排序

7 ans=0;8 foriinrange(0,n):

9 j=a[i][0]

10 whilej0: #查找截止日期之前的空时间

11 ifnotdays[j]: #找到空时间

12 days[j]=True

13 print(作业[%d,%d]在第%d天完成%(a[i][0],a[i][1],j))

14 break

15 j-=1

16 ifj==0: #没有找到空时间

17 ans+=a[i][1] #累计惩罚值

18 print(不能完成作业[%d,%d],惩罚%d

%(a[i][0],a[i][1],a[i][1]))

19 returnans;7.5哈夫曼编码;构造一棵哈夫曼树;利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。

哈夫曼树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。;证明算法的正确性，也就是证明如下两个命题是成立的。

命题7.4两个最小权值字符对应的结点x和y必须是哈夫曼树中最深的两个结点且它们互为兄弟。

命题7.5设T是字符集C对应的一棵哈夫曼树，结点x和y是兄弟，它们的双亲为z，显然有wz=wx+wy，现删除结点x和y，让z变为叶子结点，那么这棵新树T1一定是字符集C1=C-{x，y}∪{z}的最优树。;;;问题描述：有n（1≤n≤30）块石头，每块石头的重量都是正整数（重量为1～1000）。每一回合从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为x和y??且x≥y。那么粉碎的可能结果如下：

如果?x=y，那么两块石头都会被完全粉碎。

如果?x≠y，那么重量为y的石头将会完全粉碎，而重量为x的石头新重量为x-y。

最后最多只会剩下一块石头，求此石头的重量，如果没有石头剩下结果为0。;选石头的过程与构造哈夫曼树的过程类似，只是这里选的是两块最重的石头。

用优先队列（大根堆）求解，每次出队两块最重的石头x和y，然后将x-y进队，直到仅有一块石头为止。

由于heapq默认为小根堆，为此将进队的整数加上负号，在出队时再加上负号进行恢复，从而变为大根堆。;1 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,0

7???????while?maxpq:

8??????? x=-heapq.heappop(maxpq)

9?????????if?not?maxpq:return?x?? #若x是最后的石头，返回x

10??????? y=-heapq.heappop(maxpq)?? #否则再出队y

11???????? heapq.heappush(maxpq,-(x-y))? #粉碎后为x-y

12????? return?x;