资源简介

(共26张PPT)
课时37 贪心算法
一、贪心算法的基本概念
1. 概念：贪心算法是一种在每一步选择中都采取当前状态下的最好或最优解，从而希望得到全局最好或最优结果的算法。
2. 核心思想：通过局部最优的累积，达到全局最优。
3. 局限性：贪心算法只能解决一些具有特定性质（如最优子结构和贪心选择性质）的问题，它并不能保证所有问题都能得到全局最优解。
（1）贪心选择性质：每一步的局部最优能达到全局最优，即每一步的最优选择不会影响后续的选择。
（2）最优子结构：问题的最优解包含其子问题的最优解。
1. 问题建模：确定问题的选择标准和目标。
2. 选择贪心策略：明确每一步的最优选择方法。
3. 验证正确性：证明贪心策略满足最优子结构和贪心选择性质。
二、贪心算法的核心步骤
1.硬币找零问题。
（1）问题描述：用最少数量的硬币凑出金额 n，硬币面值为[1,5,10,20,50,100]。
（2）贪心策略：每次选择面值最大的硬币，直到凑够金额。
三、贪心算法的经典问题与 Python 实现
（3）Python 实现。
def coin_change(n,coins):
coins.sort(reverse=True) #按面值从大到小排序
count=0
res=[]
for coin in coins:
while n>=coin:
n-=coin
res.append(coin)
count+=1
return count,res
coins=[1,5,10,20,50,100]
n=65
print(coin_change(n,coins)) #输出：(3, [50, 10, 5])
（4）局限性：若硬币面值为非标准面值，贪心可能失效。例如，若面值为[1,3,4]，要凑出金额 6，则采用贪心算法的结果是 4+1+1（3 枚），但最优解是 3+3（2 枚）。
2.活动选择问题。
（1）问题描述：在多个活动中选择最多的不重叠活动，每个活动有开始时间和结束时间。
（2）贪心策略：按结束时间升序排序，每次选择最早结束且不与已选活动冲突的活动。
（3）Python 实现。
def a_select(a):
a.sort(key=lambda x: x[1]) #按结束时间升序排序
selected=[a[0]] #首先选择结束时间最早的活动
last_end=a[0][1] #最近一个已选活动的结束时间
for start,end in a[1:]:
if start>=last_end: #不与已选活动冲突
selected.append((start,end))
last_end=end
return selected
#a 中每个元素包含开始时间和结束时间
a=[(1,4),(3,5),(0,6),(5,7),(8,9)]
print(a_select(a)) #输出：[(1,4), (5,7), (8,9)]
典例 1 ［2025 强基联盟］某学校的大学生艺术中心将在周日面
向全校各个学院的学生社团开放，但活动中心同时只能供一个社
团活动使用，并且每一个社团活动开始后都不能中断。现在各个
社团都提交了他们使用该中心的活动计划，包括活动名称、活动
开始时间和结束时间）。
　　编写程序进行活动安排，为安排尽可能多的社团活动，要求
从结束时间最早的活动项目开始选择。例如，有 5 个活动的开
始与结束时间如图 a 所示，先按申请时间的先后（即申请的顺
序）给活动编号，再按结束时间进行升序排序，结果如图 b 所
示，则最佳活动安排序列为 1,4,3。
（1）若申请的社团活动数据如图 c 所示，则最佳活动安排序列为　　　　　　　。
（2）定义 node_list(lst)函数对申请数据进行预处理，参数 lst的数据格式为[[活动名称 1,开始时间,结束时间],[活动名称 2,开始时间,结束时间],…]。函数功能为按顺序为每个活动编号，并将 lst 内的时间数据转换为分钟（以 07:00 为起始时间）存入新列表，请在画线处填入合适的代码。
def node_list(lst):
n=len(lst);q_lst=[[0]*3 for i in range(n)]
for i in range(n):
q_lst[i][0]=i #按申请顺序编号
for j in range(1,3):
　　　　　　　 1
h=int(time[0:2]);m=int(time[3:])
q_lst[i][j]=h*60+m-7*60
return q_lst
1,5,4,6
time=lst[i][j]
（3）主程序输出安排的具体活动名称和时间，请在画线处填入合适的代码。
#读取当天的活动申请数据存入 lst中，代码略
'''定义 sort_task(q_lst)函数，对列表 q_lst 中的数据按结束时间进行升序排序，代码略'''
n=len(lst);q_lst=node_list(lst);sort_task(q_lst)
ans=[0];t=q_lst[0][2]
for i in range(1,n):
if 　　　①　　　:
t=q_lst[i][2];ans.append(q_lst[i][0])
print("活动安排如下：")
for i in range(len(ans)):
print(　　　②　　　)
q_lst[i][1]>=t
lst[ans[i]]
胜券点拨1
明考向 本题主要考查贪心算法的应用
审关键 按结束时间排序
考场思维快闪 （1） 首先将活动数据按结束时间升序排序。排序后，从结束时间最早的活动开始选择，选择条件是活动开始时间晚于或等于上一个被选中活动的结束时间
（2） 遍历每个申请数据，提取开始时间和结束时间赋值给time变量，然后提取小时和分钟部分计算出以07:00为起始时间的分钟数存入新列表q_lst中，故填入代码为time=lst[i][j]
（3） ①若当前活动的开始时间（q_lst[i][1]）大于等于上一个被选中活动的结束时间（t），则可以安排当前活动，故填入代码为q_lst[i][1]>=t。②输出安排的具体活动名称和时间。lst是活动申请数据，ans中存储的是被选中活动的编号，故填入代码为lst[ans[i]]
典例 2 ［2025 浙江名校协作体］在某答题竞赛中，每个团队都拥有 n 名选手。比赛结束后，每名选手都会有答题速度和答题准确率 2 个数据。每个团队需要从自己团队中选择 k 名（1（1）若某团队有 6 名选手，其答题速度和答题准确率如图所示，现需要选择 3 名选手来参与计分，则可获得的最大得分为　　　　　　　。
6.8
选手 答题速度 答题准确率
选手1 2 0.5
选手2 10 0.4
选手3 3 0.3
选手4 1 0.9
选手5 5 0.7
选手6 8 0.2
（2）定义如下 insertL(h,i)函数，功能是将新的选手 i 插入到 k 人名单中。
def insertL(h,i):
q=h;p=data[q][2]
while p!=-1 and data[i][0]>data[p][0] :
q=p;p=data[q][2]
data[i][2]=p;data[q][2]=i
若 data 为[[8,0.2,-1],[3,0.3, 3],[10,0.4,-1], [2,0.5,2],[5,0.7,-1],[1,0.9, -1]]，k 为 4，调用 insertL(1,4)函数，加框处语句执行的次数为　　　　　　　。
2
m=k;i=head+1
while iwhile m>1:
insertL(head,i)
m-=1;i+=1
if 　　　②　　　:
data[head][2]=data[data[head][2]][2]
insertL(head,i)
i+=1
p=head;ans=0
while p!=-1:
ans+=data[p][0]
p=data[p][2]
　　　③　　　1
if ans>maxt:
maxt=ans
for i in range(n):
data[i][-1]=-1
print("团队可获得的最大得分：",round(maxt,1))
（3）实现上述功能的部分 Python 程序如下，请在画线处填入合适的代码。
def sorta(data):
for i in range(n):
for j in range(　　　①　　　):
if data[j][1]>data[j+1][1]:
data[j],data[j+1]=data[j+1],
data[j]
'''读取某个团队的 n 名选手的数据，依次存入列表 data 的 data[0]至 data[n-1]中，data[i]包含答题速度和答题准确率 2 个数据项；读取每个团体要选择的计分人数 k，代码略'''
sorta(data)
for i in range(n):
data[i].append(-1)
maxt=0
for head in range(n-k+1):
n-i-1　或　n-2,i-1,-1
idata[data[head][2]][0]
ans*=data[head][1]
胜券点拨2
明考向 本题考查冒泡排序、链表、贪心算法思想
审关键 遍历所有可能的“最低准确率”，将该准确率作为基准，选择速度总和最大的k人组合
考场思维快闪 （1） 结合题干给出的计分规则，选择选手1、选手2以及选手5来参与计分可获得最大得分，该团队的最终得分=(2+10+5)×0.4=6.8
（2） 结合题干给出的数据可知，调用insertL(1,4)后访问的子链表表头h为1，初始q为1，p为3，进入while循环，q为3，p为2，此时data[i][0]（3） ①若从前往后进行冒泡排序，则填入代码为n-i-1；若从后往前进行冒泡排序，则填入代码为n-2,i-1,-1。②以答题准确率为关键词升序排序后，将每次取出的元素作为头节点，继续往后遍历元素，并按答题速度升序将其组织在同一链表中，元素个数达到k后，若data还有其他未被遍历的元素，且答题速度更大，则将其插入到k人名单中，故填入代码为idata[data[head][2]][0]。③ans的值为所选的k名选手答题速度之和，data中的数据按照答题准确率为关键词升序排序，head指向的节点即为所选的选手中答题准确率最低的选手，故填入代码为ans*=data[head][1]
典例 3 ［2024 北斗星盟］小明想研制一种药物，他采集了 n 种原料，现需要对每种原料的成分进行精密的分析。每种原料的分析都必须依次经过如下两个步骤：先进行放射试验，再进行加热试验。因为实验室里只有一台放射试验仪器和一台加热试验仪器，所以，同一时间最多只能做一个放射试验和一个加热试验。为尽早完成试验，小明将放射试验用时短的尽量排前面，加热试验时间用时短的尽量排后面。例如，有 A~E 共 5 种原料，每种原料需要的试验时间如图 a 所示，最终各原料的试验安排如图 b 所示。
　　编写 Python 程序，给定各种原料所需试验的时间，根据上述方法安排试验顺序并计算所有原料完成试验的最早结束时间。请回答下列问题：
若 task=[["A",5,2],["B",4,2],["C",1,8]]，n=3：
①调用该函数后，st 的值为　　　　　　　，ed 的值为　　　　　　　。
②将加框处代码改成“for j in range(n-1,-1,-1)”，
　　　　　　　（单选：A. 会 / B.不会）影响原料试验的安排顺序。
③画线处应填入的正确代码为　　　　　　。
（1）定义如下 order(task,n)函数，功能是安排试验顺序，使得试验尽早完成。其中参数 task 的每个元素由原料名称、放射试验时间和加热试验时间 3 个数据项组成，参数 n 为原料种类。
def order(task,n):
f=[False]*n;st=-1;ed=n
for i in range(n):
min=30000
for j in range(n) :
if f[j]==False:
for k in range(1,3):
if task[j][k]min=task[j][k]
bestj=j;bestk=k
　　　　　　　1
if bestk==1:
st+=1;odr[st]=bestj
else:
ed-=1;odr[ed]=bestj
0
1
A
f[bestj]=True
odr=[-1]*n
order(task,n)
#输出原料的试验顺序和最早结束时间，代码略
（2）实现上述功能的部分 Python 程序如下，请在画线处填入合适的代码。
def CalTime():
tm=[0]*n #各原料完成放射试验的时间
tm[0]=task[odr[0]][1]
for i in range(1,n):
　　　①　　　1
tot=0
for i in range(n):
j=odr[i]
if tot>tm[i]:
　　　②　　　1
else:
tot=tm[i]+task[j][2]
return tot
'''读取原料试验数据，并存储在列表 task 中。 task[i]由原料名称、放射试验时间和加热试验时间 3 个数据项组成，代码略'''
n=len(task)
tm[i]=tm[i-1]+task[odr[i]][1]
tot+=task[j][2]
胜券点拨3
明考向 本题主要考查贪心算法、排序算法
审关键 将放射试验用时短的尽量排前面，加热试验时间用时短的尽量排后面
考场思维快闪 （1） 若最短时间为放射试验时间，则从前往后排（st累加1）；若最短时间为加热试验时间，则从后往前排（ed累减1）。①原料C的放射试验时间最短，则排在最前（st=0）；原料A的加热试验时间第二短，则排在最后（ed=2）；原料B的加热试验时间第三短（先遍历到A），则排在倒数第二（ed=1）。②语句“for j in range(n-1,-1,-1)”表示从后往前进行排序，当最短时间一样时，将先排后面再排前面，会影响原料实验的安排顺序。③修改已排好的原料状态，故填入代码为f[bestj]=True
（2） ①计算每个原料的放射试验结束时间，即上一个原料的放射试验结束时间加上当前原料的放射试验时间，故填入代码为tm[i]=tm[i-1]+task[odr[i]][1]。②计算每个原料的试验结束时间，若当前总时间tot大于当前原料的放射试验结束时间tm[i]，则更新总时间为当前总时间加上当前原料的加热试验时间，故填入代码为tot+=task[j][2]
1.［2025.6 浙江选考］某校实验室有多台相同的实验仪器，每台仪器同一时间仅限一位学生使用。现要开发一个仪器预约系统，开发前先对实验室的学生进出记录进行统计分析。请回答下列问题：
（1）实验室某天09:30前学生进出情况如图a所示，09:00时实验室内的学生数为
　　 　。
图a
学号 1010 1021 3009 1010 2081 3009 1021
时间 08:00 08:05 08:20 08:45 08:50 08:50 09:15
行为 进 进 进 出 进 出 出
2
（2）定义如下函数，用于统计在实验室连续停留时间少于5分钟的学生人次。参数b列表中每个元素包含3个数据项，依次为学号、时间（用分钟表示，例如08:05表示为485）和行为（1表示进，-1表示出）。列表b用于存放某天学生进、出实验室的记录，每条进（出）的记录都有一条与之对应的出（进）记录。
def fcount(b):
　　　　　　　
i=cnt=0
while iif b[i+1][1]-b[i][1]<5:
cnt+=1
i+=2
return cnt
①要实现函数功能，方框处需实现对列表b的操作是　　　　　　　（单选）。
A.按时间排序；时间相同时，按行为由大到小
排序
B.按学号排序；学号相同时，按时间由小到大
排序
C.按行为排序；行为相同时，按学号由小到大
排序
②若函数fcount(b)的功能修改为统计“学生离开实验室后，8分钟内返回”的情况出现的次数，可将函数中画线处代码修改为：
　　　　　　　 and b[i][1]-b[i-1][1]<8。
i>0 and b[i][0]==b[i-1][0]
√
B
（3）仪器预约系统中，学生可在线预约仪器使用时段，系统按预约提交顺序逐个处理，如果预约的使用时段有仪器可用，预约成功，否则失败。
　　实现预约处理功能的函数如下，其中用到的部分列表函数与方法如图b所示，请在画线处填入合适的代码。
图b
函数与方法 功能
lst.insert(i,x) 在列表lst中下标为i的位置插入元素x。若i大于等于len(lst)，则在lst末尾添加元素x。
'''
函数参数data列表存放已按提交顺序排列的预约信息，每个元素包含4个数据项，依次为学号、起始时间、终止时间、是否成功。其中起始、终止时间都用8位数字字符串表示，如“09280830”表示9月28日8点30分；“是否成功”数据项用于存放每个预约的处理结果。
参数m存放实验室仪器台数。
'''
def proc(data,m):
a=[]
for i in range(len(data)):
　　　①　　　1
p1=0
while p1p1+=1
if p1>0:
p2=p1-1
else:
p2=0
while p2if 　　　②　　　:
flag=False
break
p2+=1
if flag:
for j in range(p1,p2):
a[j][1]+=1
a.insert(p2,[data[i][2],0])
a.insert(p1,[data[i][1],1])
if p1>0:
　　　③　　　1
a[p2+1][1]=a[p2][1]-1
data[i][3]=flag
flag=True
a[p2][1]==m
a[p1][1]=a[p1-1][1]+1
（1）学号为1010的学生08:00~08:45在实验室；学号为1021的学生08:05~09:15在实验室；学号为3009的学生08:20~08:50在实验室；学号为2081的学生08:50进入实验室，09:30未出实验室。因此09:00时实验室内的学生数为2，对应学号分别1021和2081。　（2）①根据while下面的语句可知，每个学生的进、出实验室的记录为相邻的两条记录（进的记录为b[i]，出的记录为b[i+1]），因此方框处要对列表b按学号排序，学号相同时，按时间从小到大排序。②语句“b[i][1]-b[i-1][1]<8”表示进来的时间减去上一次出去的时间小于8分钟，首先要确保存在上一次出去的记录（i>0），并确保b[i]和b[i-1]是同一学生的记录，即b[i][0]==b[i-1][0]。　（3）①使用变量flag表示是否预约成功，根据代码“flag=False”可知，初始应设置为True，故填入代码为flag=True。②根据while语句可知，变量p1查找列表a中第一个大于起始时间的索引，p2查找列表a中最后一个小于等于终止时间的索引。根据insert语句可知，a[p2][0]表示时间点，a[p2][1]表示相应的仪器使用数量。若当前时间的仪器使用数量等于m，则无法预约，故填入代码为a[p2][1]==m。③使用insert语句插入预约的起始和终止节点后，需要更新两个新节点的仪器使用数量，起始节点的仪器使用数量为上一个时间节点的数量加1，故填入代码为a[p1][1]=a[p1-1][1]+1。
2.［2025县域联盟］独桥搬箱。有k名工人，要将n个箱子从旧仓库（河右岸）搬到新仓库（河左岸），且只能通过一座桥通行。过桥规则如下：
①每次只能有一个人过桥，且右边等待的人先过桥。
②若一边有多人等待过桥，则过桥总用时短的人先过桥（过桥总用时=空手过桥用时+搬箱过桥用时）。
③若过桥总用时相同，则工人编号小的先过桥。
　　使用time记录每位工人空手过桥、到旧仓库取箱子返回桥边、搬箱过桥、放箱子到新仓库返回桥边的用时。开始时，工人们都在桥的左边等待。现计算最后一个搬运箱子的工人到达河左岸的时间。例如，n=3，k=2，time=[[1,4,1,3],[5,5,5,5]]，则最后一个搬运箱子的工人在第17分钟到达河左岸。搬箱过程如图所示。
请回答下列问题：
（1）在题干示例中，若将n改为4，则最后一个搬运箱子的工人到达河左岸的时间是第
　　　　　　　分钟。
（2）定义如下insertQue(quetype,i)函数，实现工人i在桥左边或右边排队，其中参数quetype表示4个状态，0表示空手过桥状态，1表示到旧仓库取箱子返回桥边的状态，2表示处于搬箱过桥状态，3表示放箱子到新仓库返回桥边的状态。
def insertQue(quetype,i):
que[i]=-1
if head[quetype]==-1:
head[quetype]=i
else:
p=head[quetype]
while p!=-1:
if quetype in [0,2]:
if time[p][0]+time[p][2]>
time[i][0]+time[i][2]:
break
if time[p][0]+time[p][2]==
time[i][0]+time[i][2] and p>i:
break
else:
if finishtime[p]>=finishtime[i]:
break
q=p
p=que[p]
if p==head[quetype]:
que[i]=p
head[quetype]=i
else:
que[q]=i
que[i]=p
若quetype为0，i为2，head=[1,-1,-1,-1]，que=[-1,0,-1]，time=[[10,10,5,8],[3,5,2,2],[1,8,3,10]]，则执行语句insertQue(0,2)后，head的值更新为
　　　　　　　，que的值更新为　　　　　　　。
26
[2,-1,-1,-1]　
[-1,0,1]
（3）实现搬运箱子功能的部分Python程序如下，请在画线处填入合适的代码。
'''读取箱子总数n、工人总数k、工人用时time。time中每个元素包含4个数据项，分别对应每个工人的空手过桥、到旧仓库取箱子返回桥边、搬箱过桥、放箱子到新仓库返回桥边的用时，代码略'''
#记录每个工人取放箱子的结束时间
finishtime=[-1]*k
head=[-1,-1,-1,-1]
que=[-1]*k
#开始时工人们都在桥的左边等待
for i in range(len(time)):
insertQue(0,i)
　　　①　　　1
curtime=0
while fn!=0:
#情况1：桥右边有工人在排队过桥
if head[2]!=-1:
fn-=1
w=head[2]
curtime=curtime+time[w][2]
if fn==0:
print("最后一个搬运箱子的工人到达河左岸 的时间：",curtime)
break
　　　②　　　1
finishtime[w]=curtime+time[w][3]
insertQue(3,w)
elif n>0 and head[0]!=-1:
n-=1
w=head[0]
'''情况2：桥左边的工人w过桥，代码略'''
else:
#情况3：两边都没有人在排队过桥
wh=head[1]
wh2=head[3]
if wh!=-1 and wh2!=-1:
　　　③　　　1
elif wh!=-1:
curtime=finishtime[wh]
else:
curtime=finishtime[wh2]
'''到旧仓库取箱子返回桥边再排队，放箱子到新仓库返回桥边再排队，代码略'''
fn=n
head[2]=que[w]　或　head[2]=que[head[2]]
curtime=min(finishtime[wh],finishtime[wh2])　或　curtime=min(finishtime[head[1]],finishtime[head[3]])　或其他等价答案
（1）根据题干描述，当n=3时，最后一个箱子由工人0在第17分钟到达河左岸，加上放箱子的时间为20分钟。而工人1完成放箱子到新仓库返回桥边的用时为21分钟。因此，当n=4时，最后一个箱子由工人0完成，搬运箱子的工人0到达河左岸的时间为20+1+4+1=26分钟。　（2）当前函数是将工人i插入到队列quetype中，head=[1,-1,-1,-1]、que=[-1,0,-1]表示工人1在等待过桥，此时排在工人1后面的工人0也在等待过桥，语句insertQue(0,2)表示将工人2插入到等待过桥队列中，因为工人2总用时更短，所以其排到了工人1的前面，故更新后的head为[2,-1,-1,-1]，que为[-1,0,1]。　（3）①根据下面代码可知，变量f存储未到达河左岸（新仓库一侧）的箱子数量，右侧排队的工人每过一次桥，fn递减1，故fn初始值为箱子总数n。②当桥右边有工人在排队过桥时，变量w为当前队首元素，即右岸排队的第一个工人，curtime存储当前时间（当前时间加上工人搬箱过桥的时间），若这是最后一个箱子（fn==0），则按要求输出最后一个搬运箱子的工人到达河左岸的时间，此时结束循环，原队首元素出队完成处理后，应更新当前队首元素（head[2]=que[w]）和工人取放箱子的结束时间，并将当前完成状态2处理的工人加入状态3处理。③若桥两边都没有人在排队过桥，说明状态0和状态2没有待处理元素，此时判断状态1和状态3的情况：若状态1和状态3队列均非空，则比较两个队首元素完成当前处理步骤的时间，将时间更新为两个步骤中先完成处理步骤的完成时间，故填入代码为curtime=min(finishtime[wh],finishtime[wh2])。

展开更多......

收起↑