送礼物（算法竞赛进阶指南 P105，双向搜索）

一.题目链接：

送礼物

二.题目大意：

大容量背包问题.

三.分析：

直接搜会 T 掉，那么就双向搜索.

先搜一半，把答案记录下来，再搜后一半，二分查找即可.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;

const int M = (int)1e5;
const int mod = 99991;
const int inf = 0x3f3f3f3f;

ll w, ans;
ll a[(1<<24) + 5];
int n, m, g[50], len;

void dfs1(int u, ll sum)
{
    if(u == m)
    {
        a[len++] = sum;
        return;
    }
    dfs1(u + 1, sum);
    if(sum + g[u] <= w)
        dfs1(u + 1, sum + g[u]);
}

ll cal(ll sum)
{
    ll x = w - sum;
    int l = 0, r = len - 1, mid;
    while(l < r)
    {
        mid = (l + r + 1) >> 1;
        if(a[mid] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    return a[l] + sum;
}

void dfs2(int u, ll sum)
{
    if(u == n)
    {
        ans = max(ans, cal(sum));
        return;
    }
    dfs2(u + 1, sum);
    if(sum + g[u] <= w)
        dfs2(u + 1, sum + g[u]);
}

int main()
{
    scanf("%lld %d", &w, &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &g[i]);
    sort(g, g + n), reverse(g, g + n);
    m = n / 2 + 2;
    dfs1(0, 0);
    sort(a, a + len + 1), len = unique(a, a + len + 1) - a;
    dfs2(m, 0);
    printf("%lld\n", ans);
    return 0;
}