如果问题不但具有“初态”，还具有明确的“终态”，并且从初态开始搜索与从终态开始逆向搜索产生的搜索范围能覆盖整个问题的状态空间，在这种情况下，可以采用双向搜索——从初态和终态出发各搜索一半状态，使得两边的搜索深度减半，在中间交会、组合成最终的答案。
例题：P10484 送礼物
这个问题的直接解法就是进行“指数型”的枚举——搜索每个礼物选还是不选，时间复杂度为 \(O(2^N)\)。当然，若搜索过程中已选的礼物重量之和已经大于 \(W\)，可以及时剪枝。
但是此题 \(N \le 45\)，\(2^{45}\) 的计算量很大。这时就可以利用双向搜索的思想，把礼物分成两半。
首先，搜索出从前一半礼物中选出若干个，可能达到的 \(0 \sim W\) 之间的所有重量值，存放在一个数组中，并对数组进行排序、去重。
然后，进行第二次搜索，尝试从后一半礼物中选出一些。对于每个可能达到的重量值 \(w\)，在第一部分得到的数组中二分查找 \(\le W-w\) 的数值中最大的一个，用二者的和更新答案。
这个算法的时间复杂度就只有 \(O(2^{N/2} \log 2^{N/2}) = O(N \cdot 2^{N/2})\) 了，还可以加入一些优化，进一步提高算法的效率，比如把礼物按照重量降序排序后再分半、搜索。
参考代码
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
int g[50], mid, n, maxw, ans;
vector<int> w;
// 第一阶段 DFS：搜索前 mid 个物品的所有可能重量组合
void dfs1(int u, int sum) {if (u == mid) {w.push_back(sum);return;}// 不选当前物品dfs1(u + 1, sum);// 选当前物品（需判断是否超过 maxw）if (sum <= maxw - g[u]) {dfs1(u + 1, sum + g[u]);}
}
// 第二阶段 DFS：搜索剩余物品，并结合第一阶段结果更新最大值
void dfs2(int u, int sum) {if (u == n) {// 二分查找第一个使得 w[i] + sum <= maxw 的最大 w[i]int t = maxw - sum;auto it = upper_bound(w.begin(), w.end(), t);if (it != w.begin()) {it--;ans = max(ans, sum + *it);}return;}// 不选dfs2(u + 1, sum);// 选if (sum <= maxw - g[u]) {dfs2(u + 1, sum + g[u]);}
}
int main()
{scanf("%d%d", &maxw, &n);for (int i = 0; i < n; i++) scanf("%d", &g[i]);// 优化：从大到小排序，优化搜索效率sort(g, g + n, greater<int>());mid = n / 2;// 执行第一阶段dfs1(0, 0);// 对结果排序并去重，方便二分查找sort(w.begin(), w.end());w.erase(unique(w.begin(), w.end()), w.end());ans = 0;// 执行第二阶段dfs2(mid, 0);printf("%d\n", ans);return 0;
}