acwing算法提高之搜索--剪枝

1 介绍

本专题用来记录使用dfs剪枝技巧求解的题目。

剪枝有以下思路：

1. 优化搜索顺序。
2. 可行性剪枝。
3. 最优性剪枝。
4. 唯一性剪枝，也叫去除冗余。
5. 记忆化搜索，也叫dp。

2 训练

题目1：165小猫爬山

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int N = 20;
int n, m;
vector<int> a;
vector<vector<int>> group;
int res = 20;bool check(int x, int j) {int s = 0;for (auto v : group[j]) s += v;return s + x <= m;
}void dfs(int i, int groupsize) {if (groupsize >= res) {//最优性剪枝return;}if (i == n) {res = groupsize;}int x = a[i];//将x放入哪个组for (int j = 0; j < groupsize; ++j) {//将x放入第j组if (check(x, j)) { //可行性剪枝group[j].emplace_back(x);dfs(i + 1, groupsize);group[j].pop_back();}}//新开一个组group[groupsize].emplace_back(x);dfs(i + 1, groupsize + 1);group[groupsize].pop_back();return;
}int main() {cin >> n >> m;a.resize(n + 1);for (int i = 0; i < n; ++i) cin >> a[i];group.resize(n + 1);sort(a.begin(), a.end());reverse(a.begin(), a.end()); //从大到小枚举，优化搜索顺序//放置原则dfs(0, 0);cout << res << endl;return 0;
}

题目2：