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：