描述
作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1)以下的任意多个物品。GY希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i],G[i]<= 2^31-1。
输出格式
仅一个整数，表示GY在他的力气范围内一次性能搬动的最大重量。
样例输入
20 5 7 5 4 18 1
样例输出
19
数据范围与约定
- 对于20%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1
题解：利用双向搜索的思想，将礼物分成两半。首先，搜索出从前一半礼物中选取若干个，可能达到的 0~w 之间的所有重量值，存放在 s 数组中，并对 s 数组进行排序。然后进行第二次搜索，尝试从后一半礼物中选出一些。对于每个可能达到的重量值 val，在 s 数组中二分查找 <= w-val 的数值中最大的一个，用二者的和更新答案即可。P105
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 100000005;
ll a[55], s[maxn];
ll ans, n, w, tot;void dfs1(ll x, ll val) {if(x > n) {s[++tot] = val;return ;}if(a[x] + val <= w)dfs1(x+1, a[x]+val);dfs1(x+1, val);
}void dfs2(ll x, ll val) {if(x >= (n+1)>>1) {ll l = lower_bound(s+1, s+tot+1, w-val) - (s+1);ans = max(ans, val+s[l]);return ;}if(a[x] + val <= w) dfs2(x+1, a[x]+val);dfs2(x+1, val);
}
int main()
{std::ios::sync_with_stdio(false);cin >> w >> n;for(int i = 1; i <= n; i++)cin >> a[i];sort(a+1, a+n+1);ll mid = (n+1)>>1;dfs1(mid, 0);sort(s+1,s+tot+1);dfs2(1, 0);cout << ans << endl;return 0;
}