双向BFS和前面的双向DFS思路基本一样，都是为了从两端搜索从而避免搜索中间一大块复杂的情况

送礼物

原题链接

达达帮翰翰给女生送礼物，翰翰一共准备了 $N$ 个礼物，其中第 i 个礼物的重量是 $G[i]$。

达达的力气很大，他一次可以搬动重量之和不超过 $W$ 的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表 $W$ 和 $N$。

以后 $N$ 行，每行一个正整数表示 $G[i]$。

输出格式

仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围

$1 ≤ N ≤ 46,$
$1 ≤ W , G[i] ≤ 2^{31}−1$

输入样例

输出样例

题意

给出背包体积和每个物品体积，问一次最多装多少物品

思路

看数据范围判断背包问题一定会TLE，但N范围比较小，因此使用爆搜，把所有可能方案枚举一遍，取一个最大值
但是直接爆搜，时间复杂度 2^46^，也是会超时的

优化——双向DFS 用空间换时间
先枚举前一半数能凑出来的集合，再枚举后一半数，然后在两个集合中分别找 $a、b$，看能不能找到使$a+b<=w$（$w$是要求的最大总重量）
爆搜b，二分查找a，借此优化时间复杂度

本题思路总结如下：

将所有物品重量从大到小排序
先将前k件物品能凑出的所有重量打表，然后排序判重

搜索剩下的n-k件物品的选择方式，然后在表中二分出不超过w的最大值

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 46;

using i64 = long long;

int n, m;
int k;
int w[N]; // 每个物品重量
int weights[1 << 25], cnt; // 能凑出来的重量
int ans; // 全局最小值

void dfs1(int u, int s) // u:枚举到哪个数 s:当前的和
{
    if (u == k)
    {
        weights[cnt ++ ] = s;
        return;
    }

    dfs1(u + 1, s); // 不选第u个
    if ((i64)s + w[u] <= m) dfs1(u + 1, s + w[u]); // 选第u个
}

void dfs2(int u, int s)
{
    if (u == n)
    {
        // 二分查找前一部分
        int l = 0, r = cnt - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (weights[mid] <= m - s)  l = mid;
            else r = mid - 1;
        }
        ans = max(ans, weights[l] + s); // 更新答案
        return;
    }

    dfs2(u + 1, s); // 不选第u个
    if ((i64)s + w[u] <= m) dfs2(u + 1, s + w[u]); // 选第u个
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    // 从大到小排序
    sort(w, w + n);
    reverse(w, w + n);

    // 对前k个数打表预处理
    k = n / 2; // 防止n==1死循环
    dfs1(0, 0);

    // 排序去重
    sort(weights, weights + cnt);
    cnt = unique(weights, weights + cnt) - weights; // 返回当前数组长度

    dfs2(k, 0); // 爆搜后一部分
    
    cout << ans << '\n';
}