首页 > 代码库 > 深度优先搜索

深度优先搜索

2024-07-24 15:11:23   220人阅读

深度优先搜索（DFS， Depth-First Search）是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后退到前一步的状态，如此不断重复，直至找到最终的解。

部分和问题

给定整数a1、a2、……、an，判断是否可以从中选出若干个数，使它们的和恰好为k。

限制条件

  • 1 ≤ n ≤ 20
  • -108 ≤ ai ≤ 108
  • -108 ≤ k ≤ 108

输入

n = 4

a = {1,2,4,7}

k =13

输出

Yes

 

从a1开始按顺序决定每个数加或不加，在全部n个数都决定后再判断它们的和是不是k即可。因为状态数是2n+1，所以复杂度是O(2n)。代码如下：

 1 #include <iostream> 2 #include <vector> 3 using namespace std; 4  5 int n, k; 6 vector<int> a; 7  8 //已经从前i项得到了sum，然后对于i项之后的进行分支 9 bool dfs(int i, int sum)10 {11     //如果前n项都计算过了，则返回sum是否与k相等12     if (i == n) return sum == k;13 14     //不加上a[i]的情况15     if (dfs(i+1, sum)) return true;16 17     //加上a[i]的情况18     if (dfs(i+1, sum+a[i])) return true;19 20     //无论是否加上a[i]都不能凑成k就返回false21     return false;22 }23 24 int main()25 {26     while (cin >> n)27     {28         int tmp;29         for (int i = 0; i < n; i++)30         {31             cin >> tmp;32             a.push_back(tmp);33         }34         cin >> k;35         if (dfs(0, 0))36             cout << "Yes" << endl;37         else38             cout << "No" << endl;39     }40     return 0;41 }

 

深度优先搜索


联系
我们