【算法专题】从倍数分组问题看 DFS 回溯算法的底层逻辑

1. 题目背景数字王国的军训分队在算法竞赛或面试中我们经常遇到“将 N 个物体按某种规则分配到最少数量的组”的问题。今天这道题就是一个典型的例子核心规则同一队内任何两个数字不能存在倍数关系包括相同数字。目标求最少分队数。数据范围0n10。虽然数据范围很小但它背后隐藏的递推与搜索思想非常值得深挖。2. 深度解析为什么选择 DFS面对这类“方案搜索”问题我们通常有三种思考维度贪心每次选一个能放下的队放进去。错误局部最优不代表全局最少可能导致后面的人无处可去动态规划 (DP)寻找状态转移。可行但由于分组状态难以压缩实现较复杂DFS 回溯穷举所有可能的分组情况通过“剪枝”优化。本题的最优解核心思维模型决策树当我们处理第 i 个数字时它面临两个抉择抉择 A加入已有的 k 个队伍中的某一个前提是满足非倍数关系。抉择 B如果不想加入老队伍或者老队伍都容不下它则新开一个队。通过递归我们实际上是在遍历一棵决策树。每走到一个叶子节点即所有人都分好了就记录一次队伍总数最后取最小值。3. 算法实现的三大法宝① 状态定义我们需要记录idx: 当前处理到第几个学生。teams: 当前已经分出的队伍集合每个队内部是一个列表。② 冲突检测Check判定规则必须双向a % b 0或b % a 0。因为 2 是 4 的约数4 也是 2 的倍数只要满足其一两人就不能同队。③ 剪枝优化Pruning—— 效率的关键这是 DFS 的灵魂如果当前分出的队伍数已经 大于 之前找到的最小答案那么这条分支就没必要再走下去了。这大大减少了计算量。4. Python 代码实现带详细注释import sys import os def can_add(name,team): for member in team: if name%member0 or member%name0: return False return True def dfs(idx): global ans if len(teams)ans: #剪枝 return #递归终点 if idxn: anslen(teams) return cur_studenta[idx] #当前学生 #策略一尝试将当前学生放进现有的每一个合法队伍中 #使用range(len(teams))是因为在循环中我们会修改teams内部的元素 for i in range(len(teams)): if can_add(cur_student,teams[i]): teams[i].append(cur_student) #进队 dfs(idx1) teams[i].pop() #回溯出队尝试下一种可能 #策略二新开辟一个队伍 teams.append([cur_student]) dfs(idx1) teams.pop() #回溯撤回新开的队伍 nint(input()) alist(map(int,input().split())) ansn #记录全局最小队伍数 teams[] #列表的每个元素也是一个列表代表一个队伍中的成员名字 dfs(0) print(ans)5. 总结与复盘通过这道题我们不仅学会了如何处理倍数冲突更掌握了DFS 解决分组问题的标准模板分岔路口选老队还是新开队回溯本质在递归返回后务必还原状态pop操作确保不影响其他分支的尝试。剪枝艺术在搜索树中及时“剪掉”那些不可能产生更优解的枝条。