ACWING171. 送礼物（双向搜索）

本文主要是介绍ACWING171. 送礼物（双向搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

达达帮翰翰给女生送礼物，翰翰一共准备了N个礼物，其中第i个礼物的重量是G[i]。

达达的力气很大，他一次可以搬动重量之和不超过W的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式
第一行两个整数，分别代表W和N。

以后N行，每行一个正整数表示G[i]。

输出格式
仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围
1≤N≤46,
1≤W,G[i]≤231−1
输入样例：
20 5
7
5
4
18
1
输出样例：
19

思路：
数据范围小首先考虑状压和搜索。
这是一个背包问题，我们知道背包问题的状态定义是背包容量，2e9的级别是放不下的。
而直接搜，2⁴⁶也不行的。

考虑折半，先爆搜处理完前一半的所有选择状态。
再爆搜处理后一半的所有选择状态。
后一半的选择结果，加上在前一半里面的选择结果不大于容量就是合理的，这个寻找过程可以二分处理。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;typedef unsigned int ui;
int cnt,half;
int n;
ui a[(1 << 24) + 1],g[105],ans,w;int cmp(int a,int b)
{return a > b;
}void Find(ui val)
{ui res = w - val;int l = 1,r = cnt,answ = 0;while(l <= r){int mid = (l + r) >> 1;if(a[mid] <= res){answ = mid;l = mid + 1;}else{r = mid - 1;}}ans = max(ans,a[answ] + val);
}void dfs1(int i,ui sum)
{if(i == half){a[++cnt] = sum;return;}dfs1(i + 1,sum);if(g[i] + sum <= w)dfs1(i + 1,sum + g[i]);
}void dfs2(int i,ui sum)
{if(i == n + 1){Find(sum);return;}dfs2(i + 1,sum);if(g[i] + sum <= w)dfs2(i + 1,sum + g[i]);
}int main()
{scanf("%u%d",&w,&n);for(int i = 1;i <= n;i++){scanf("%d",&g[i]);}sort(g + 1,g + 1 + n,cmp);half = n / 2 + 3;dfs1(1,0);sort(a + 1,a + 1 + cnt);cnt = unique(a + 1,a + 1 + cnt) - (a + 1);dfs2(half,0);printf("%u\n",ans);return 0;
}