CH 2401 送礼物(进阶指南，双向搜索)

算法竞赛进阶指南，111 页，双向搜索，先搜一半，再搜一半

本题要点：
1、数据直接用 long long 来存，避免溢出麻烦
2、从大到小排序，先处理前一半的数据， 看看可以组合出来哪些 数的和是 小于等于 w的（ 和 <= w）。
用 vector 存储这些和，去重，排序。这里使用vector的 unique 函数 和erase 函数。
3、 处理后面一半，得到若干数的和 为sum（sum <= w）。
然后在 vector 中二分查找， 最大的一个数 k 使得， k + sum <= w;
这里使用了 stl的 算法 upper_bound

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MaxN = 50;
long long w, ans, g[MaxN], n, m;
vector<long long> v;bool cmp(long long a, long long b)
{
    return a > b;
}//从 后往前依次处理每个数据
//正在处理第cur 位置，后面cur + 1 ~ n / 2 的位置已经处理好
//累加和为sum
void dfs_l(int cur, long long sum)
{
    if(0 == cur){
    v.push_back(sum);return;}dfs_l(cur - 1, sum);	// 不选择 curif(sum + g[cur] <= w){
    dfs_l(cur - 1, sum + g[cur]);// 选择 cur}
}//从前往后先后处理每个数据
void dfs_r(int cur, long long sum)
{
    if(cur == n + 1){
    int y = *(--upper_bound(v.begin(), v.end(), w - sum));ans = max(ans, y + sum);return;}dfs_r(cur + 1, sum);// 不选择 curif(sum + g[cur] <= w){
    dfs_r(cur + 1, sum + g[cur]);// 选择 cur}
}int main()
{
    scanf("%lld%lld", &w, &n);for(int i = 1; i <= n; ++i){
    scanf("%lld", &g[i]);}sort(g + 1, g + n + 1, cmp);int k = n / 2 + 3;dfs_l(k - 1, 0);sort(v.begin(), v.end());vector<long long>::iterator new_end = unique(v.begin(), v.end());v.erase(new_end, v.end());dfs_r(k, 0);printf("%lld\n",ans);return 0;
}/* 20 5 7 5 4 18 1 *//* 19 */