python 基础知识点（蓝桥杯python科目个人复习计划38）

本文主要是介绍python 基础知识点（蓝桥杯python科目个人复习计划38），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日复习内容：DFS的剪枝

我理解的剪枝，和《运筹学》里面“分支定界法”的剪枝操作一样，不停按照题目所给条件分割，当所得目标函数的值已偏离最优解时，就将其减去。

例题1：数字王国之军训排队

题目描述：

数字王国开学了，它们也和我们人类一样有军训，现在一共有n名学生，每个学生有自己的一个名字ai（数字王国里的名字就是一个整数，注意学生们可能出现重名的情况），此时叛逆教官来看了之后感觉十分别扭，决定将学生重新分队。

排队规则为：将学生分成若干队，每队里面至少一名学生，且每队里面学生的名字不能出现倍数情况（名字相同也是一种倍数情况）

例：有4名学生（2，3，4，4），最少可以分成（2，3），（4），（4）共三队。

输入格式：

第一行包含一个正整数n，表示学生数量；

第二行包含n个由空格隔开的整数，第i个整数表示第i个学生的名字ai。

输出格式：

输出共一行，包含一个整数，表示最少可以分成几队

思路：

DFS搜索：枚举每个学生分到每个组内

可行性剪枝：满足题目条件

最优性剪枝：判断当前状态是否比ans更劣

参考答案：

# 检验x能否加入该组
def check(x,group):# 不能存在倍数关系for y in group:if x % y == 0 or y % x == 0:return Falsereturn Truedef dfs(depth):global ansif len(Groups) > ans:  #  剪枝returnif depth == n:ans  = min(len(Groups),ans)return#  枚举for each_group in Groups:if check(a[depth],each_group):each_group.append(a[depth])dfs(depth + 1)each_group.pop()# 单独一组时Groups.append([a[depth]])dfs(depth + 1)Groups.pop()n = int(input('请输入一个整数：'))
a = list(map(int,input('请输入一系列数字：').split()))
ans = n
# 分组情况
Groups = []
dfs(0)
print(ans)

运行结果：