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

2020-01-11 16:00:29来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

例题:

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

例题分析:

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

或者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 是在这张抽象的图上进行的,但我们不必把这张图真正地建立出来。


原文链接:https://www.cnblogs.com/littlefrog/p/12179828.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Java固定资产管理系统 源码 jsp ssh

下一篇:开源项目SMSS开发指南(二)——基于libevent的线程池