035 搜索之DFS基础

DFS：深度优先搜索——本质上是暴力枚举，尽可能一条路走到底，走不了回退

1.DFS与n重循环

例：给定一个数字x，将其拆分为3个正整数，后一个要求大于前一个，给出方案。

分析：这种情况下就可以三重暴力循环破解

如果要拆分成n个正整数，就要实现n重循环

答题模板：不知道要进行多少次循环=n重循环=特定的树结构=DFS搜索

# 从用户处获取输入，x 表示生成序列中数字的和以及每个位置数字的取值上限（1 到 x）
# 最终生成的序列里所有数字相加要等于 x，且每个数字的取值范围是 1 到 x
x = int(input("请输入数字的和以及每个位置数字的取值上限 x: "))
# 从用户处获取输入n 表示要生成的序列深度
# 也就是最终生成的序列包含多少个数字
n = int(input("请输入要生成的序列的长度 n: "))

# 初始化用于存储当前生成序列的列表 path
# 先创建空列表，之后将其初始化为长度为 n 的列表，每个元素初始值为 0
# path 列表将在后续深度优先搜索过程中逐步填充数字，代表当前正在生成的序列
path = []
path = [0] * n

# 定义深度优先搜索函数 dfs，depth 表示当前正在处理序列的第几层
# last_value 表示上一层选择的数字，用于保证生成的序列是递增的
def dfs(depth, last_value):
    # 递归出口条件：当 depth 等于 n 时，说明已经生成了一个完整的长度为 n 的序列
    if depth == n:
        # 检查序列中所有数字的和是否等于输入的 x
        # 只有和为 x 的序列才是符合我们要求的序列
        if sum(path) != x:
            return
        # 如果序列中数字的和等于 x，则打印该序列
        print(path)
        return
    # 枚举当前位置（第 depth 个位置）可以取的值，范围是从 last_value 到 x
    # 从 last_value 开始枚举能保证生成的序列是递增的，避免生成重复或递减的序列
    for i in range(last_value, x + 1):
        # 下一层从上一层的起点+1开始
        # 比如说第一层选 3，第二层就要从 3 开始枚举，前面的 1 和 2 就不用考虑了，这样能保证是递增的
        # 将当前枚举的值 i 赋给序列的第 depth 个位置
        path[depth] = i
        # 递归调用 dfs 函数，处理下一个位置（depth + 1）
        # 同时将当前选择的数字 i 作为下一层的 last_value 传入，确保后续枚举是递增的
        dfs(depth + 1, i+1)

# 启动深度优先搜索，从序列的第一个位置（depth = 0）开始
# 初始时上一层没有选择数字，所以 last_value 设为 0
dfs(0, 0)

#请输入数字的和以及每个位置数字的取值上限 x: 7
# 请输入要生成的序列的长度 n: 3
# [0, 1, 6]
# [0, 2, 5]
# [0, 3, 4]
# [1, 2, 4]

提炼模板

def dfs(depth):
    #当前为第几重循环
    if depth==n: #如果是最后一重循环
        return
    #每重循环的枚举选择

#分析：七个小朋友，所以是七重循环，n=7
       # 每个小朋友得到的糖果2-5  2<=x<=5
ans=0
def dfs(depth,n,m):
    if depth==7:
        if n==0 and m==0:
            global ans
            ans=ans+1
        return
    #枚举当前小朋友的糖果可能性
    #枚举第一种糖果
    for i in range(0,6):
        for j in range(0,6):
            if 2<=i+j<=5 and i<=n and j<=m:
                dfs(depth+1,n-i,m-j)
dfs(0, 9, 16)
print(ans)
# 5067671

# 分析：n重循环，每重循环三种情况：买一个，买半个，不买
def dfs(depth,weight,count):
    if weight>m:  #当前已经不合法，没必要继续下去
        return
    if weight==m:
        global ans
        ans=min(ans,count)
    #depth:第depth个瓜
    #weight:表示当前买到的瓜的重量
    #count:表示劈了多少次
    if depth==n:
        return
    #枚举瓜的三种情况
    #不买
    dfs(depth+1,weight+0,count)
    #买
    dfs(depth+1,weight+a[depth],count)
    #买一半
    dfs(depth+1,weight+a[depth]//2,count+1)

n,m=map(int,input().split())  #n表示n个瓜，m表示要买的重量
m=m*2  #为了比避免出现小数影响精度，所以都乘2

a=list(map(int,input().split()))  #表示每个瓜的重量
a=[x*2 for x in a]
ans=n+1
dfs(0,0,0)
if ans==n+1:
    ans=-1
print(ans)