1. 基本概念

• 单向搜索：传统的搜索算法（如广度优先搜索 BFS、深度优先搜索 DFS）通常从起点开始，逐步扩展搜索到目标节点。搜索的时间复杂度与图的大小和结构有关。

• 双向搜索：双向搜索则同时从起点和终点进行搜索，两个搜索分别扩展，直到在中间相遇。因为每次搜索的深度都减少了一半。

2. 核心思想

双向搜索通过减少单向搜索的路径长度来提高效率。假设图的深度为 d，如果使用广度优先搜索（BFS）从起点到终点进行单向搜索，时间复杂度是 O(b^d)（其中 b 是图的分支因子）。而双向搜索则从起点和终点同时进行搜索，时间复杂度为 O(b^(d/2) + b^(d/2))，即 O(b^(d/2))。

题目 

 题解：

首先暴力的复杂度为 （每个值加或不加），肯定是不行的（2^40），但是如果能将其分解为两个(2^20) ，这题就能被解决。

• 计算前一半的所有子集和：
  • 通过递归或迭代的方法，枚举前一半题目的所有可能组合，计算它们的和，并存储到一个数组 b 中。大约时间复杂度2^20 （1e6）
• 计算后一半的所有子集和：
  • 类似地，枚举后一半题目的所有可能组合，计算它们的和，并在后续结合前一半的子集和进行处理（我们对b数组进行排序和去重，得到排序数组 ，我们再对另一半进行搜索）。
  • 对于后一半的每一个子集和 sum2，在 b 中查找满足 sum1 + sum2 <= T 的最大 sum1，从而更新最大时间和 maxSum。
  • 最终，maxSum 即为符合条件的最大和。

    #include<bits/stdc++.h>using namespace std;
    using ll = long long;
    const int N = 50,M = 1e7+10;
    int n,t,cnt;
    ll a[N],b[M],ansMax;
    void dfsPre(int k,ll sum)
    {if(sum > t) return ;b[cnt++] = sum;// 先记录b数组，在判断:// 不论当前路径的 sum 是通过选择当前元素还是不选择当前元素产生的// 它都应该被记录到 b 数组中，以确保不会遗漏任何一个可能的子集和if(k >= (n + 1) / 2) return ;// 选a[k]和不选a[k]两种选择dfsPre(k + 1, sum + a[k]);dfsPre(k + 1, sum);}
    void dfsSuf(int k, ll sum){if(sum > t) return ;if(k > n) return ;// 考虑前半部分，二分查找b数组 + sum最大的不超过t的值int l = 0, r = cnt - 1;while(l < r){int mid  = (l + r + 1) >> 1;if(b[mid] + sum <= t) l = mid;else r = mid - 1;}if(b[r] + sum <= t) ansMax = max(ansMax,b[r] + sum);dfsSuf(k + 1, sum + a[k]);dfsSuf(k + 1, sum);}
    int main() {cin >> n >> t;for(int i = 0; i < n; i++) cin >> a[i];// a数组前半部分进行搜索dfsPre(0,0);// 对b数组进行排序以及去重sort(b, b + cnt);cnt = unique(b, b + cnt) - b;// a数组后半部分进行搜索dfsSuf((n + 1) / 2 , 0);cout << ansMax;return 0;
    }