oi笔记——抽象的深度优先搜索

例题：

\(N个数中选K个数，选出的和要为sum\)

例题分析：

对于每个点，我们可以按“选”和“不选”进行搜索，如图：

或者01背包求解

求解示例（抽象深搜版代码）

#include <iostream>

using namespace std;

int n, k, sum, ans;

int a[40];

void dfs(int i,int cnt,int s) {

    if(i==n) {

        if(cnt==k&&s==sum) {

            ans++;

        }

        return;

    }

    dfs(i+1,cnt,s);

    dfs(i+1,cnt+1,s+a[i]);

}

int main() {

    cin >> n >> k >> sum;

    for (int i = 0; i < n; i++) {

        cin >> a[i];

    }

    ans = 0;

    dfs(0,0,0);

    cout<<ans<<endl;

    return 0;

}

定义：

前面说过，dfs 看起来是运行在图上的搜索算法，而前一节给大家展示的 dfs 过程，我们没有看到图的存在，这就是抽象形式的 dfs 的特点。我们可以根据搜索状态构建一张抽象的图，图上的一个顶点就是一个状态，而图上的边就是状态之间的转移关系（进一步搜索或回溯）。虽然 dfs 是在这张抽象的图上进行的，但我们不必把这张图真正地建立出来。

巴特西

oi笔记——抽象的深度优先搜索

oi笔记——抽象的深度优先搜索

例题：

例题分析：

求解示例（抽象深搜版代码）

最新文章

热门文章