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 False
        return True



def dfs(depth):
    global ans
    if len(Groups) > ans:  #  剪枝
        return
    if 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)

运行结果：