当前位置: 首页 > news >正文

蓝桥杯 之 回溯之充分剪枝

文章目录

    • 买瓜
    • 最大数字

  • 在蓝桥杯当中,对于回溯是属于一个必考的问题,但是除了回溯的几个基本的问题,如果通过剪枝来提前删去无效的分支,以大大减少时间复杂度是需要我们进一步思考的问题!
  • 回溯的基本问题:
    • 回溯的初始状态
    • 回溯的状态转移
    • 回溯的结束状态
  • 其中,这个剪枝的考点就可以在结束状态部分进行充分的考察
  • 那么这个剪枝有哪些思路与思考?
    • 对于这个n个物体,求和的回溯问题:可以考虑使用前缀和,排序两个手段进行提前剪枝(以真题买瓜进行深入的分析)

买瓜

买瓜

在这里插入图片描述

  • 首先按照正常的回溯的思路:

    • 首先考虑在回溯的过程中,我们需要记录什么参数?
      • 由于要更新这个最终的切西瓜的刀数,所以得设置一个变量记录当前的切西瓜的刀数
      • 那么当前是切的哪一个西瓜?所以还得记录一下这个所处理的西瓜的下标
      • 那么怎么知道当前的得到的西瓜的重量?所以还得设置一个变量去记录当前所得到的西瓜
    • 总的来说,回溯的过程中,需要三个变量(i, k, cursum),分别表示当前处理到的西瓜的下标,当前已经切的西瓜刀数,当前得到的西瓜的重量
  • 考虑这个结束的状态与更新答案的状态

    • 结束的状态:当处理到的西瓜的下标达到n的时候,就返回(因为西瓜的下标是从0开始的,所以当处理到的西瓜的下标到达n就说明已经处理完了)
    • 更新的状态:当当前的重量等于目标重量的时候,就比较当前的切西瓜的次数与当前的切西瓜的最优次数,进行一个更新
  • 由于有除以2的操作,所以我们可以将这个目标都扩大两倍,同时将这个西瓜重量也扩大两倍,这样就不用除以2

# 对于每个西瓜,可以选择切与不切
n, m = map(int, input().split())
m = m<<1 
num = list(map(int, input().split()))
a = [i*2 for i in num]
ans = n+1
# 当前的瓜的下标,当前切的刀数,当前的重量
def dfs(i, k, cursum):global ansif cursum == m:ans = min(ans, k)if i == n:return# 不选dfs(i + 1, k, cursum)# 选择,如果当前的cursum 没有超过这个mif cursum + num[i] > m:return# 选择一整个西瓜dfs(i + 1, k, cursum + a[i])# 选择半个西瓜dfs(i + 1, k + 1, cursum + num[i])
dfs(0,0,0)
print(ans if ans != n+1 else -1)
  • 思考:剪枝不够充分,目前的剪枝是有对结束状态的判断,那么还有什么情况可以考虑?
    • 考虑及时加上全部的西瓜仍然<m,这个时候就没有必要递归下去了,直接结束(难道我们每次都得使用这个sum函数进行求解吗?当然不是,我们可以使用前缀和进行求解,但是为了方便起见,得将原始的数组和前缀和数组进行转置)
    • 如果当前的重量已经超过了这个 m就没有必要继续递归下去了
# 总的来说,m,n是输入
n,m = map(int,input().split())
m = m << 1
num = list(map(int,input().split()))
num.sort()
a = [i<<1 for i in num]
pre = [0]*n
pre[0] = a[0]
for i in range(1,n):pre[i] = pre[i-1] + a[i]
a = a[::-1]
pre = pre[::-1]
ans = n+1
def dfs(i,k,cursum):global ansif cursum == m :ans = min(ans,k)# if k >= ans:#     returnif i == n or cursum >= m or cursum + pre[i] < m:returndfs(i+1,k,cursum )dfs(i+1,k+1,cursum + a[i] // 2)dfs(i+1,k,cursum + a[i])dfs(0,0,0)
print(ans if ans != n+1 else -1)

最大数字

最大数字
在这里插入图片描述

  • 错误的递归思路:每次只要么处理一位操作1要么处理操作2,这样的处理思路是有问题的,你要么在位数i的时候,直接用完对应的操作1或者操作2,使其变为9,如果不能变为9,那么就尽可能大(操作2是有可能剩余的,但是操作1是不可能剩余的)
  • 包含一点贪心的思路
import os
import sys# 请在此输入您的代码# 肯定是按照这个数位进行操作的
N,A,B = map(int,input().split())
N = list(str(N))
n = len(N)
# 需要记录什么?操作1的次数,操作2的次数,当前操作的是哪一位?
ans = 0
def dfs(i,n1,n2,curnum):global ansif i == n:ans = max(ans,curnum)return # 先进行加法,看看能不能将该位变为9num = int(N[i])ad = min(n1,9-num)n1 -= ad dfs(i+1,n1,n2,curnum*10 + num + ad)n1 += ad # 进行减法if n2 > num:n2 = n2 - (num + 1)dfs(i+1,n1,n2,curnum*10 + 9)n2 = n2 + (num + 1)
dfs(0,A,B,0)
print(ans)

http://www.mrgr.cn/news/94397.html

相关文章:

  • Docker基础命令说明
  • 【技术白皮书】内功心法 | 第二部分 | Telnet远程登录的工作原理
  • 芯片研发不需要PPT
  • 计算机视觉|首次写入政府工作报告!这个科技新词“具身智能”到底是什么?
  • 【NLP 33、实践 ⑦ 基于Triple Loss作表示型文本匹配】
  • Linux---VI/VIM编辑器
  • 【算法】数组、链表、栈、队列、树
  • LeetCode 第8题:字符串转换整数 (atoi)
  • 个性化音乐推荐系统
  • 【菜鸟飞】通过vsCode用python访问公网deepseek-r1等模型(Tocken模式)
  • onnxruntime-gpu与cuda版本对应及是否能调用cuda测试
  • C盘清理技巧分享:释放空间,提升电脑性能
  • 色板在数据可视化中的创新应用
  • vue3 中使用 Recorder 实现录音并上传,并用Go语言调取讯飞识别录音(Go语言)
  • Xxl-Job学习笔记
  • python学习笔记-mysql数据库操作
  • excel中两个表格的合并
  • 网络通信(传输层协议:TCP/IP ,UDP):
  • 【MySQL】基本操作 —— DDL
  • django框架 [面试篇]