AcWing 171. 送礼物（搜索）

深度优先 + 双向搜索

双向搜索：将整个需要搜索的对象分成两半（在已知初态与终态的时候可以考虑）

原题链接

感悟：首先可能会思考动态规划，但它的时间复杂度是（nv）v太大了，不适合。n比较小，可以考虑爆搜。然后这里有个非常好的技巧，就是把原数据分成两半，在通过一些技巧，剪枝，可以有效的降低时间复杂度。

本题思路

1. 先搜索前 N / 2 的数据，枚举所有可能的重量集合，存入数组
2. 对所有重量集合排序，从大到小（顺序优化），判重（排除冗余）
3. 在搜索后一半，枚举所有可能的重量集合，然后当前集合X与前面的数组中一个集合Y，是得X+Y <= m，且X+Y是最大的
4. 然后就是到枚举结束输出最大的X+Y

剪枝及优化

• 双向搜索的思路就大大降低了时间复杂度
• 对于从什么地方开始分开也有讲究：前一半的为 2^(N/2) 后一半为 2^(N/2)*o(二分)，所以可以中和下，可在 N/2 + 2 时分开
• 搜索顺序的优化： 从大到小
• 判重： STL 中的unique可以实现数组中的判重，也可以自己写一个不难

ACcode

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;

int n, m, k;
int weights[1 << 24], g[50];
int cnt = 0, ans = 0;

void dfs_1(int u, int sum)
{
    if(u == k)
    {
        weights[cnt++] = sum;
        return;
    }
    
    if((LL)sum + g[u] <= m) dfs_1(u+1, sum+g[u]);
    dfs_1(u+1, sum);
}

void dfs_2(int u, int sum)
{
    if(u == n)
    {
        int l = 0, r = cnt -1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(weights[mid] + (LL)sum <= m) l = mid;
            else r = mid - 1;
        }
        if(weights[l] + (LL)sum <= m) ans = max(ans, weights[l] + sum);
        return;
    }
    
    if(g[u] + (LL)sum <= m) dfs_2(u+1, g[u]+sum);
    dfs_2(u+1, sum);
}

int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i++) cin >> g[i];
    
    sort(g, g+n);
    reverse(g, g+n);
    
    k = n/2 + 2;
    dfs_1(0, 0);
    
    sort(weights, weights+cnt);
    int t = 1;
    for(int i = 1; i < cnt; i++)
        if(weights[i] != weights[i-1])
            weights[t++] = weights[i];
    cnt = t;
    
    dfs_2(k, 0);
    
    cout << ans << endl;
    
    return 0;
}