首页 > 代码库 > 基础1暴力之枚举
基础1暴力之枚举
深度优先搜索(DFS,Depth-First Search)是搜索手段之一。它从某个状态开始,不断的转移状态知道无法转移,然后退回到前一步的状态,继续转移到其他状态,如此不断重复,直到找到最终的解。
问题给定整数a1,a2...an,判断是否可以从中选出若干数,使它们的和恰好为k。
1<=n<=20
-1e8<=ai<=10e8
-1e8<=k<=1e8
输入:
n=4 k=13
a={1 2 4 7}
输出:
Yes (13 = 2 + 4 + 7)
输入:
n=4 k=15
a={1 2 4 7}
输出:
No
枚举每一种情况复杂度为O(2^n)。利用dfs搜索可以枚举每一种情况代码如下:
#include <iostream> #include<stack> #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include <math.h> using namespace std; #define pi acos(-1) const int N=1e5; int n,a[N],ans[N],k; int h=0; bool dfs(int i,int sum)//i代表第i个数(从0开始) { if(i==n) return sum==k; if(dfs(i+1,sum+a[i])) //加入a[i]往下递归 { ans[h++]=a[i]; return true; } if(dfs(i+1,sum))//不加a[i]往下递归 可以看成是加不加a[i]的问题(包括了所有状态) { return true; } return false; } int main() { int i,j; while(scanf("%d%d",&n,&k)!=EOF) { h=0; for(i=0; i<n; i++) scanf("%d",&a[i]); if(dfs(0,0)) { printf("Yes (%d =",k); for(i=0; i<h; i++) { printf(" %d",ans[i]); if(i!=h-1) printf(" +"); } printf(")\n"); } else printf("No\n"); } return 0; }
基础1暴力之枚举
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。