DFS暴力搜索——选与不选模型
DFS暴力搜索：选与不选模型
所有「从n个物品中选若干个，满足某种条件求最优解/统计方案数」的问题，本质都可以用最朴素的DFS暴力枚举：每个物品只有两种选择——选，或者不选。我们用递归按顺序遍历所有物品，在递归过程中维护当前选择的状态，遍历完所有物品时统计答案。
这个模型的核心框架高度统一，区别仅在于不同题目需要维护不同的业务参数。搜索过程中可加入少量可行性判断，提前剪掉绝对无效的分支，提升运行效率。
优点：对符合上述描述的问题，可以快速获得解决方案
缺点：时间复杂度为指数级O(2^n)，只能解决30内的数据
一、基础模型：P1036 [NOIP 2002 普及组] 选数
问题重述
已知 n 个整数 $x_1,x_2,\cdots,x_n$，以及 1 个整数 k（k < n）。从 n 个整数中任选 k 个整数相加，计算得到的和为素数的情况共有多少种。
输入样例：
4 3
3 7 12 19输出样例：
1（唯一符合条件的组合：3+7+19=29）
第一步：定义DFS参数
DFS函数需要三个核心参数，对应当前搜索状态：
idx：当前处理到第几个数cnt：已经选了多少个数sum：当前选中数字的总和
第二步：搜索逻辑
对于第 idx 个数，我们有且仅有两种选择：
- 不选：直接处理下一个数，
cnt和sum不变 - 选：把当前数加入总和，
cnt+1，sum += x[idx]，然后处理下一个数
搜索中可加入两处可行性判断，减少无效递归：若已选数量超过k，或是剩余未处理的数全选也凑不够k个，直接终止当前分支。
第三步：递归边界
当 idx > n 时，所有数都处理完毕。此时恰好选了 k 个数，就判断 sum 是否为素数，是则答案加1。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, k;
int x[N];
int ans = 0;
bool is_prime(int num) {
if (num < 2) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
// 编号 已选总量 已选总和
void dfs(int idx, int cnt, int sum) {
// 可行性判断：已选超量 / 剩余全选也不够，直接终止
// （属于速度优化 可以不加）
if (cnt > k) return;
if (cnt + (n - idx + 1) < k) return;
if (idx > n) {
if (is_prime(sum)) ans++;
return;
}
// 不选当前数
dfs(idx + 1, cnt, sum);
// 选当前数
dfs(idx + 1, cnt + 1, sum + x[idx]);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
dfs(1, 0, 0);
cout << ans << endl;
return 0;
}这就是选与不选模型的标准模板：两层递归分别对应两种选择，按顺序逐个处理物品，边界处统计结果。
二、用选与不选模型解决动态规划问题
动态规划中的背包、最长子序列等问题，本质都是「每个物品选或不选」的决策。小数据范围下，直接用DFS暴力枚举所有选法，完全可以得到正确答案。
2.1 P1048 [NOIP 2005 普及组] 采药
问题重述
有T单位时间和M株草药，采每株草药需要花费一定时间，同时获得对应价值。在总时间不超过T的前提下，求能获得的最大总价值。
输入样例：
70 3
71 100
69 1
1 2输出样例：
3（选第2、3株，时间69+1=70，价值1+2=3）
思路
每株草药只有采或不采两种选择。维护两个状态：已用时间、当前总价值。如果采当前草药不超时，就可以选；最终在所有合法方案中取价值最大值。
可预处理后缀价值和做预判：如果当前价值加上剩余所有草药的总价值，都无法超过已找到的最大价值，就没有继续搜索的必要。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int M = 105;
int T, m;
int t[M], val[M];
int suf_val[M]; // 后缀价值和：第i~m株的总价值
int max_val = 0;
// 编号 已用时间 已获得总价值
void dfs(int idx, int time_used, int cur_val) {
if (idx > m) {
max_val = max(max_val, cur_val);
return;
}
// 最优性预判：剩余全采也超不过当前最大值，直接终止
// （属于速度优化 可以不加）
if (cur_val + suf_val[idx] <= max_val) return;
// 不采
dfs(idx + 1, time_used, cur_val);
// 采：时间不超就可以选
if (time_used + t[idx] <= T) {
dfs(idx + 1, time_used + t[idx], cur_val + val[idx]);
}
}
int main() {
cin >> T >> m;
for (int i = 1; i <= m; i++) {
cin >> t[i] >> val[i];
}
// 预处理后缀和
for (int i = m; i >= 1; i--) {
suf_val[i] = suf_val[i + 1] + val[i];
}
dfs(1, 0, 0);
cout << max_val << endl;
return 0;
}2.2 P2362 围栏木桩
问题重述
有n根按编号排列的木桩，高度为h[i]。从中选若干根保持原顺序，要求高度非降（后一根不小于前一根）。求选出木桩的最大数量t，以及达到最大数量的方案总数c。
输入包含m组测试数据。
输入样例：
3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12输出样例：
4 1
2 2
3 3思路
每根木桩选或不选。选的话需要满足：当前木桩高度 ≥ 上一根选中的木桩高度。维护当前序列长度和上一根高度，遍历所有方案，统计最长长度及对应方案数。
可加入预判：如果当前序列长度加上剩余木桩总数，也达不到已找到的最长长度，直接终止当前分支。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int m, n;
int h[N];
int max_len = 0;
int cnt = 0;
// 编号/上一个选了的高度/已选总量
void dfs(int idx, int last_h, int len) {
// 最优性预判：剩余全选也达不到当前最长长度，直接终止
// （属于速度优化 可以不加）
if (len + (n - idx + 1) < max_len) return;
if (idx > n) {
if (len > max_len) {
max_len = len;
cnt = 1;
} else if (len == max_len) {
cnt++;
}
return;
}
// 不选
dfs(idx + 1, last_h, len);
// 选：必须满足非降条件
if (h[idx] >= last_h) {
// last更新为当前木桩高度，已选总量+1
dfs(idx + 1, h[idx], len + 1);
}
}
int main() {
cin >> m;
while (m--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
max_len = 0;
cnt = 0;
dfs(1, 0, 0);
cout << max_len << " " << cnt << endl;
}
return 0;
}三、用选与不选模型解决贪心问题
贪心算法的最优解，同样可以通过DFS暴力枚举所有选择来验证。对于小数据范围的题目，不用推导贪心策略，直接爆搜即可出答案。
3.1 P2672 [NOIP 2015 普及组] 推销员
问题重述
螺丝街有N家住户，第i家距离入口S_i米，推销会积累A_i点疲劳值。从入口进入，推销完原路返回，总疲劳值 = 所有推销住户的A_i之和 + 2 × 最远住户的距离。
对于每个X（1 ≤ X ≤ N），求恰好推销X家住户时，能积累的最大疲劳值。
输入样例：
5
1 2 2 4 5
5 4 3 4 1输出样例：
15
19
22
24
27思路
每户只有去或不去两种选择。维护当前选了多少户、A值总和、最远距离。遍历所有组合，对每个X更新对应的最大疲劳值。
可预处理A值后缀和做预判，提前剪掉无法刷新对应户数最大值的分支。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n;
int s[N], a[N];
int suf_a[N]; // 后缀A值和
int ans[N]; // ans[x]表示选x户的最大疲劳值
// 编号/已选总户数/累计推销疲劳值/已选户中的最大距离
void dfs(int idx, int cnt, int sum_a, int max_s) {
if (idx > n) {
if (cnt > 0) {
ans[cnt] = max(ans[cnt], sum_a + 2 * max_s);
}
return;
}
// 最优性预判：剩余全选也无法刷新对应户数的最大值，直接终止
// （属于速度优化 可以不加）
int rest = n - idx + 1;
if (sum_a + suf_a[idx] + 2 * max_s <= ans[cnt + rest]) return;
// 不选
dfs(idx + 1, cnt, sum_a, max_s);
// 选
dfs(idx + 1, cnt + 1, sum_a + a[idx], max(max_s, s[idx]));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) cin >> a[i];
// 预处理后缀和
for (int i = n; i >= 1; i--) {
suf_a[i] = suf_a[i + 1] + a[i];
}
memset(ans, 0, sizeof ans);
dfs(1, 0, 0, 0);
for (int i = 1; i <= n; i++) {
cout << ans[i] << endl;
}
return 0;
}3.2 P1803 凌乱的yyy / 线段覆盖
问题重述
有n场比赛，每场有开始时间a_i和结束时间b_i。不能同时参加多场比赛，求最多能参加几场。
输入样例：
3
0 2
2 4
1 3输出样例：
2（选第1、2场，0-2和2-4）
思路
每场比赛选或不选。选的话必须满足：本场开始时间 ≥ 上一场结束时间。维护上一场结束时间和已选场数，求最大值。
可加入预判：如果当前已选场数加上剩余所有比赛数，也超不过已找到的最大值，直接终止搜索。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n;
int a[N], b[N];
int max_cnt = 0;
// 编号/上一场参加考试结束时间/已选考试总量
void dfs(int idx, int last_end, int cnt) {
// 最优性预判：剩余全选也超不过当前最大值，直接终止
// （属于速度优化 可以不加）
if (cnt + (n - idx + 1) <= max_cnt) return;
if (idx > n) {
max_cnt = max(max_cnt, cnt);
return;
}
// 不选
dfs(idx + 1, last_end, cnt);
// 选：时间不冲突
if (a[idx] >= last_end) {
dfs(idx + 1, b[idx], cnt + 1);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
dfs(1, 0, 0);
cout << max_cnt << endl;
return 0;
}四、模型总结
通用框架
所有选与不选的DFS代码，都遵循完全一致的结构，可根据题目需求加入合理性预判：
void dfs(当前处理到第几个, 业务参数1, 业务参数2, ...) {
if (满足终止条件) return;
if (所有物品处理完) {
更新答案;
return;
}
// 不选当前物品
dfs(idx + 1, 业务参数不变);
// 选当前物品（满足条件时）
if (满足选择条件) {
dfs(idx + 1, 更新后的业务参数);
}
}适用范围与局限
- 适用场景：n ≤ 20 时，总共有 $2^n$ 种组合，暴力枚举不会超时；加入合理预判后可支持稍大规模的数据
- 优点：思路直白，不用推导复杂的状态转移或贪心策略，代码结构固定，不易写错
- 缺点：本质仍是暴力枚举，时间复杂度为 $O(2^n)$，n 增大后会快速超时，此时需要改用动态规划或贪心算法
- 用途：没其他思路时做保底分，或者和你的其他思路对拍（随机假设数据并在两种代码下运行，看结果是否一致）
评论已关闭