资源简介

(共24张PPT)
课时38 回溯算法
一、回溯算法的基本概念
1. 概念：回溯算法是一种通过递归和剪枝解决问题的算法策略。
2. 核心思想：试错。在尝试所有可能解的过程中，若发现当前路径无法得到有效解，则回退到上一步，选择其他路径继续探索。
1. 选择：在当前步骤选择一个可能的选项，并记录路径。
2. 递归：基于当前选择进入下一层决策。
3. 回溯：若发现当前路径无效，则返回上一层并撤消选择。
二、回溯算法的核心步骤
1. 全排列问题。
（1）问题描述：给定一个数组 nums，生成其所有可能的排列。
（2）回溯策略：每次选择一个未被使用的元素，加入当前排列，递归处理剩余元素。当排列长度等于数组长度时，记录结果并回溯。
三、回溯算法的经典问题与 Python 实现
（3）Python 实现。
def permute(nums):
def backtrack(path,used): #used 标记已选元素
if len(path)==len(nums):
#若排列长度等于数组长度，则记录排列
res.append(path[:])
return
for i in range(len(nums)):
if not used[i]: #若元素还未使用
used[i]=True #标记元素为已使用
path.append(nums[i]) #选择当前元素
backtrack(path,used) #递归
path.pop() #回溯，撤消选择
used[i]=False
res=[]
backtrack([],[False]*len(nums))
return res
nums=[1,2,3]
print(permute(nums))
#输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
（4）回溯过程图示。
2. 子集问题。
（1）问题描述：给定一个数组 nums，生成其所有可能的子集。
（2）回溯策略：每次选择一个元素加入当前子集，递归处理后续元素。记录所有长度的子集。
（3）Python 实现。
def subsets(nums):
def backtrack(start,path): #通过 start避免重复子集
res.append(path[:]) #记录当前子集
for i in range(start,len(nums)):
path.append(nums[i]) #选择当前元素
backtrack(i+1,path) #递归处理后续元素
path.pop() #回溯，撤消选择
res=[]
backtrack(0,[]) #从空子集开始回溯
return res
nums=[1,2,3]
print(subsets(nums))
#输出：[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
1. 剪枝：在递归过程中提前终止不可能得到有效解的路径。
2. 示例：组合总和问题。
（1）问题描述：给定数组 nums和目标值 t，找出所有和为 t的组合（数组元素可以重复选择）。
（2）剪枝策略：若当前路径的和已经超过 t，则直接返回上一层，提前终止该路径的递归。
四、回溯算法的剪枝优化
（3）Python 实现。
def combination_sum(nums,t):
def backtrack(start,path,remain):
if remain==0:
#若当前和为 t，则记录组合
res.append(path[:])
return
for i in range(start,len(nums)):
if nums[i]>remain:
continue #剪枝，跳过不可能的解
path.append(nums[i]) #选择当前元素
backtrack(i,path,remain-nums[i]) #递归
path.pop() #回溯
res=[]
nums.sort() #排序，便于剪枝
backtrack(0,[],t)
return res
nums=[2,3,6,7]
t=7
print(combination_sum(nums,t)) #输出：[[2,2,3],[7]]
典例 1 小明计划在一天内参观某城市的多个景点，每个景点需要一定的参观时间（小时）和费用（元）。他希望选择若干景点（至少 2 个景点），使得总时间不超过 5 小时且总费用不超过 100 元，且每个景点只能选择一次。编写程序找出所有满足条件的景点组合。
（1）若该城市的景点及对应的参观时间和费用如图所示，则共有　　　　　　　种满足条件的景点组合。
5
景点 参观时间（小时） 费用（元）
A 1 30
B 2 50
C 1.5 40
D 3 60
（2）实现上述功能的 Python 程序如下，请在划线处填入合适的代码。
def find(a,max_time,max_cost):
result=[]
n=len(a)
def backtrack(start,pt,pc,path):
if pt<=max_time and pc<=max_cost and len(path)>=2:
result.append(path[:])
if 　　　①　　　:
return
for i in range(start,n):
time,cost=a[i][1],a[i][2]
if 　　　②　　　:
continue
path.append(a[i][0])
backtrack(i+1,pt+time,pc+cost,
path)
start==n
pt+time>max_time or pc+cost>max_cost
　　　③　　　1
backtrack(0,0,0,[])
return result
'''读取景点数据，并存储在列表 a 中。a[i]由景点名、参观时间和费用 3 个数据项组成，例如a=[["A",1, 30],["B",2,50],["C",1.5,40],["D",3,60]]，代码略'''
max_time=5
max_cost=100
r=find(a,max_time,max_cost)
print("满足条件的景点组合：")
for i in range(len(r)):
print(r[i])
path.pop()
胜券点拨1
明考向 本题主要考查回溯算法
审关键 找出所有满足条件的景点组合
考场思维快闪 （1） 共有5种满足条件的景点组合：①A和B（3小时，80元）。②A和C（2.5小时，70元）。③A和D（4小时，90元）。④B和C（3.5小时，90元）。⑤C和D（4.5小时，100元）
（2） ①当所有景点均遍历完时，终止递归，故填入代码为start==n。②若当前景点的参观时间加上已选景点的参观时间大于5小时，或当前景点的费用加上已选景点的费用大于100元，则不会添加当前景点到当前组合，故填入代码为pt+time>max_time or pc+cost>max_cost。③回溯到前一个状态，故填入代码为path.pop()
典例 2 ［2025 浙江名校协作体］有 n 种原材料，这些材料将被用在 k 条不同的流水线进行产品加工，每个流水线所需的材料不相同。因此，要求每个流水线提出自己的材料需求，这些需求用一串 n 位，由 0、1 和-1 三种值组成的数表示，其中：1 表示当前流水线必须使用该材料；0 表示该材料可加可不加，-1 表示当前流水线不需要使用该材料。例如，“0110-1-1”表示当前流水线必须使用第 2、3 种材料，不需要使用第 5、6 种材料，第 1、4 种材料可加可不加。
现通过编程计算能否找到一个用最少种类的原材料，且能满足所有流水线材料需求的最佳原材料生产方案。若某两条流水线给出的需求如图所示 ，则最佳原材料生产方案为：110001。该由 0、1 组成的串表示编号为 1、2、6 的原材料必须生产，编号为 3、4、5 的原材料无须生产。
流水线1 流水线2
材料 编号 1 2 3 4 5 6 1 2 3 4 5 6
需求 1 1 0 -1 0 1 0 1 -1 -1 -1 1
请回答下列问题：
（1）现在有 3 种原材料，4 条流水线给出的材料需求分别为 101、1-10、001、1-11，则最佳原材料生产方案为　　　　　　　（用由 0、1 组成的串表示）。
（2）定义 chan(s,n,k)函数，将由 0、1 和-1 组成的字符串 s 转换成包含 k 个数据元素，每个数据元素包含 n 个数据项的数据存储形式。
def chan(s,n,k):
a=[[] for i in range(k)]
p=0;i=0
while pif s[p]!="-":
a[i].append(int(s[p]));p+=1
else:
a[i].append(int(s[p:p+2]));p+=2
if len(a[i])==n:
i+=1
return a
若字符串 s 的值为"110-10101-1-1-11"，则调用函数 chan(s,6,2)后，语句“i+=1”的执行次数为
　　　　　　　。
101
2
（3）实现上述功能的部分 Python 程序如下，请在划线处填入合适的代码。
'''读取原材料种类 n，流水线数量 k，k 条流水线的材料需求保存在字符串 s 中，s 的格式形如"1011-100011-11"，代码略'''
b=[0]*(n+1);a=chan(s,n,k);p=True
while 　　　①　　　:
j=n
while b[j]==1:
j-=1
b[j]=1
for i in range(j+1,n+1):
　　　②　　　1
p=False
for i in range(len(a)):
for j in range(len(a[i])):
if a[i][j]==1 and b[j+1]==0 or
　　　③　　　:
p=True
if p==True:
print("无最佳原材料生产方案！")
else:
for i in range(1,n+1):
if b[i]==1:
print("原材料",i,"必须生产")
else:
print("原材料",i,"无须生产")
p==True and b[0]==0　或其他等价答案
b[i]=0
a[i][j]==-1 and b[j+1]==1
胜券点拨2
明考向 本题主要考查回溯算法
审关键 枚举所有可能的原材料组合，验证是否满足所有流水线的需求
考场思维快闪 （1） 第1种原材料在流水线1、2、4中都必须使用，所以第1种原材料必须生产。第3种原材料在流水线1、3、4中都必须使用，所以第3种原材料必须生产。第2种原材料在4条流水线中，只存在“可加可不加”和“不需要使用”两种情况，所以第2种原材料无须生产。所以最佳原材料生产方案为101
（2） 调用函数chan(s,6,2)，即将字符串s转换成包含2个数据元素，每个数据元素包含6个数据项的列表，每提取出6个元素，i的值累加1，故语句“i+=1”共执行了2次
（3） 该程序遍历所有可能的原材料组合（二进制枚举），验证是否满足所有流水线的需求。若存在冲突（必须使用的材料未生产或不需要使用的材料被生产），则标记为无效并继续遍历。①若b[0]的值为1，则表示已遍历完所有可能组合；若p的值为False，则表示已找到最佳生产方案，退出循环，故填入代码为p==True and b[0]==0。②从后往前找到第一个b[j]==0的位置，将其置为1，并将后面所有位置的值置为0，故填入代码为b[i]=0。③如果某条流水线需要第j+1种原材料（a[i][j]==1），而当前组合中该原材料未生产（b[j+1]==0），则该组合不满足这条流水线需求；如果某条流水线不需要第j+1种原材料（a[i][j]==-1），而当前组合中该原材料被生产（b[j+1]==1），则该组合同样不满足这条流水线需求，故填入代码为a[i][j]==-1 and b[j+1]==1
1.给定n种物品和1个背包，物品i的重量是wi，其价值为vi，背包的容量为C。问：应如何选择装入背包的物品，使得装入背包中物品的总价值最大？注意：物品不能被分割，即物品i要么整个地选取，要么不选取。小明编写如下Python程序解决上述问题，请在画线处填入合适的代码。
N=3　#物品的数量
C=16　#背包的容量
w=[10,8,5]　#每个物品的重量
v=[5,4,1]　#每个物品的价值
#x[i]=1代表物品i放入背包，0代表不放入
x=[0,0,0]
CurWeight=0　#当前放入背包的物品总重量
CurValue=0　#当前放入背包的物品总价值
#最优值；当前的最大价值，初始化为0
BestValue=0
'''最优解；BestX[i]=1代表物品i放入背包，0代表不放入'''
BestX=[0]*N
def backtrack(t):
global CurWeight,CurValue,BestValue
if t>N-1:
#若找到了一个更优的解
if CurValue>BestValue:
　　　①　　　1
for i in range(N):
BestX[i]=x[i]
else:
'''遍历当前节点的子节点：0代表不放入背包，1代表放入背包'''
for i in range(2):
　　　②　　　1
if i==0:　#不放入背包
backtrack(t+1)
else:　#放入背包
if CurWeight+w[t]<=C:
CurWeight+=w[t]
CurValue+=v[t]
backtrack(t+1)
　　　③　　　1
CurValue-=v[t]
backtrack(0)
print("最优值：",BestValue)
print("最优解：")
for i in range(N):
print(BestX[i],end=" ")
BestValue=CurValue
x[t]=i
CurWeight-=w[t]
问题是n个物品中选择部分物品，可知问题的解空间是子集树。比如物品数目n=3时，其解空间树如图所示，边为1代表选择该物品，边为0代表不选择该物品。使用x[i]表示物品i是否放入背包，x[i]=0表示不放入，x[i]=1表示放入。回溯搜索过程，若来到了叶子节点，则表示一条搜索路径结束，若该路径上存在更优的解，则保存下来；若不是叶子节点，是中间的节点（如节点B），就遍历其子节点（D和E），若子节点满足条件，就继续回溯搜索子节点。在回溯算法中，遍历解空间树的所有路径，对于每一个节点，要么选择它（放入背包），要么不选择它（不放入背包）。在搜索的过程中，要考虑当前的约束条件，即背包的容量，若选择某一个物品会使背包超过其容量，则该选择无效，不再继续搜索这条路径。在代码中，已经实现了这个思路：当i==0时，表示不选择当前物品，直接回溯下一个物品；当i==1时，表示选择当前物品，但在放入物品之前会检查放入后的总重量是否超过背包容量，若超过，则不进行这一步的选择。
2.某班举行了二元一次方程组解题测试。方程均为“ax+by=c”的形式，其中a，b，c均为1~100的整数，a，b为1时省略不写。
　　测试数据存储在“test.txt”文件中，如图a所示。每个方程组由方程1和方程2组成，所有题一定有解，解一定为1~100的整数；n位学生提交的答题数据存储在对应的文件中。
　　小张编写了答题数据的批改程序，输出每位学生的答对题的数量及答对数量最多的学生数据（若有并列则均输出）。例如，n=4，程序输出效果如图b所示。
图a 图b
1 号同学答对 8 题！
2 号同学答对 9 题！
3 号同学答对 10 题！
4 号同学答对 10 题！
最多答对 10 道题！ 为 [3, 4] 号同学！
（1）主程序。
'''ans存储测试中所有题的答案，ans[i][0]、ans[i][1]分别存储第i+1题x、y的解'''
ans=[]
n=50　#学生人数
'''获取测试数据，存入列表x中，如x=[["第1题","2x+9y=81","3x+y=34"],["第2题","x+2y=21","3x+5y=56"],…]；
x的第一个数据元素表示测试第1题方程组的第1个方程是2x+9y=81，第2个方程是3x+y=34，以此类推。
代码略'''
for t in x:
#提取两个方程的数值
a1,b1,c1=remove(t[1])
a2,b2,c2=remove(t[2])
#求该题的解
jie=solve(a1,b1,c1,a2,b2,c2)
#在列表ans末尾添加一个元素
ans.append(jie)
m=0;st=[]
#判断每位学生的答题情况
for i in range(1,n+1):
'''获取当前学生答题情况存入列表st_ans中，如st_ans=[[9,7],[7,7],[3,2],…]；
st_ans[j][0]、st_ans[j][1]分别存储当前学生第j+1题所答x、y的解；
代码略'''
#cnt存储当前学生答对的题数
cnt=cal(ans,st_ans)
if cnt>m:
st=[]
st.append(i)
m=cnt
elif cnt==m:
st.append(i)
print(i,"号同学答对",cnt,"题！")
print("最多答对",m,"道题！","为",st,"号同学！")
若删除该程序段中加框的语句，　　 　　（单选：A.会 / B.不会）影响程序运行的结果。
A
（2）定义如下remove(fc)函数，功能是提取并返回方程中的数值，如fc为"3x+y=34"，返回3,1,34，请在画线处填入合适的代码。
def remove(fc):
abc=[0,0,0]
h=["+","="]
s=""
i=0
for c in fc:
if c not in h:
s=s+c
else:
if len(s)==1:
abc[i]=1
else:
　　　①　　　`
i=i+1
　　　②　　　1
abc[i]=int(s)
return abc[0],abc[1],abc[2]
abc[i]=int(s[:-1])　或其他等价答案
s=""
（3）定义如下solve(a1,b1,c1,a2,b2,c2)函数，功能是求出方程组的解，请在画线处填入合适的代码。
def solve(a1,b1,c1,a2,b2,c2):
for x in range(1,101):
　　　　　　　1
if a2*x+b2*y==c2:
return [x,y]
（4）定义如下cal(ans,st_ans)函数，功能是统计学生答对的题数并返回，请在画线处填入合适的代码。
def cal(ans,st_ans):
cnt=0
for i in range(len(ans)):
if 　　　　　　　:
cnt+=1
return cnt
y=(c1-a1*x)/b1
ans[i][0]==st_ans[i][0] and ans[i][1]==st_ans[i][1]　或　ans[i]==st_ans[i]
（1）st存储的是答对数量最多的学生数据，当cnt>m时，需要重新添加学生数据，若删除st=[]，由于st未被初始化，会输出错误的结果。　（2）①遍历fc中的字符，当遇到运算符"+"或"="时，处理其前面的子串s，当len(s)=1时，表示系数为1；当len(s)>1时，需要提取其中的数字字符（即去掉最后一个字符）转换为整数存储到abc[i]中，故填入代码为abc[i]=int(s[:-1])。②每次提取一个数值后，需要将s清空，以便处理下一个子串，故填入代码为s=""。　（3）函数solve使用枚举算法计算二元一次方程组的解。对于每个可能的x值，根据方程a1*x+b1*y=c1计算对应的y值，然后判断x和y是否满足第二个方程a2*x+b2*y=c2，若满足则返回解，故填入代码为y=(c1-a1*x)/b1。　（4）遍历ans（正确答案列表）和st_ans（学生答案列表），对于每个题目，如果学生的答案与正确答案相等，则cnt加1，故填入代码为ans[i][0]==st_ans[i][0] and ans[i][1]==st_ans[i][1]或ans[i]==st_ans[i]。

展开更多......

收起↑