文章目录
前言
一、双向DFS
二、AcWing 171. 送礼物
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：双向DFS，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、双向DFS
和 双向广搜 原理一样，都是在数据十分庞大的情况下用两端同时搜索的方法去搜索得到最优解，具体原理可见博客：双向广搜
二、AcWing 171. 送礼物
本题链接：AcWing 171. 送礼物
本博客提供本题截图：
本题解析
用到了二分法，二分法的模板和原理见博客：二分法，我们的思路是让物品一半去打表计算可能的组成的组合，我们是按照正好取半去分两组dfs，其实可以根据分析题意让其中更加复杂的部分减少递归，让简单的部分增加递归，不管是dfs1还是dfs2我们都需要传递两个参数，第一个参数代表当前枚举的是第几个物品，第二个参数代表当前选择的情况下的总重量。weights数组存储的是我们前一半的物品可能组成的重量的集合，因为每个物品都有可能拿或者不拿，所以我们的数组长度为1 << 23，dfs1的作用就是计算出weight，利用剪枝我们知道我们需要从大到小排列weight，因为我们的weight中可能有重复的元素，且我们不需要重复的元素，去除冗余的代码为：
sort(weights, weights + cnt); cnt = unique(weights, weights + cnt) - weights;
cnt代表的就是去除冗余后数组的长度，同时我们的cnt是从1开始的，因为最初的时候是没有任何重量，且什么物品都不选也是一种重量即0
dfs2的作用就是在后半部分的物品中，利用二分法找到满足s + w[u] <= m的最大s + w[u]，并且更新ans
AC代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 46; int n, m, k; int w[N]; int weights[1 << 23], cnt = 1; int ans; void dfs1(int u, int s) { if (u == k) { weights[cnt ++ ] = s; return; } dfs1(u + 1, s); //选择该物品 if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[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 ((LL)s + weights[mid] <= m) l = mid; else r = mid - 1; } ans = max(ans, s + weights[l]); return; } dfs2(u + 1, s); //不选当前的物品 if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]); //选当前的物品 } int main() { cin >> m >> n; for (int i = 0; i < n; i ++ ) cin >> w[i]; sort(w, w + n); reverse(w, w + n); k = n / 2; dfs1(0, 0); sort(weights, weights + cnt); cnt = unique(weights, weights + cnt) - weights; dfs2(k, 0); cout << ans << endl; return 0; }
三、时间复杂度
关于双向DFS的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
