送礼物（双向搜索）

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

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

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

输入格式

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

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

输出格式

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

---

emmmmm， 爆搜的话直接进行指数型枚举——枚举每个物品选还是不选， 时间复杂度为O(2ⁿ)。当然，若搜索过程中已选的礼物重量之和大于w， 可以及时剪枝。此题n <= 45 复杂度过高， 我们可以采取双向搜索， 把礼物分成两半。

首先，我们搜索出前一半礼物选出若干个， 可能到达0-w之间的所有重量值， 放在一个数组里， 对数组进行排序， 去重。

然后， 我们进行第二波搜索， 尝试从后一半礼物中选出一些。对于每个可能达到的重量t，从第一部分得到的数组中二分查找<= w - t的数组中最大的一个， 用两者的和更新答案

ps：取1 - n / 2 + 2 作为前一半， n / 2 + 3 - n为后一半， 搜索速度更快；

#include <bits/stdc++.h>using namespace std;typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 2e7 + 100; const int MAXM = 3e3 + 10;template < typename T > inline void read(T &x) {x = 0; T ff = 1, ch = getchar();while(!isdigit(ch)) {if(ch == '-') ff = -1;ch = getchar();}while(isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}x *= ff; }template < typename T > inline void write(T x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0'); }ll w, n, top = 0, tot = 0, ans, a[MAXN], b[MAXN], c[MAXN];inline bool cmp(ll x, ll y) {return x > y; }ll find(ll x) {int l = 1, r = tot;while(l < r) {int mid = (l + r + 1) / 2;if(c[mid] <= x) l = mid;else r = mid - 1;}return c[l]; } void dfs(ll x, ll val) {if(x == n / 2 + 3) {b[++top] = val;return ;} if(val + a[x] <= w) dfs(x + 1, val + a[x]);dfs(x + 1, val); }void DFS(ll x, ll val) {if(x == n + 1) {ll u = find(w - val);ans = max(ans, u + val);return ;}if(val + a[x] <= w) DFS(x + 1, val + a[x]);DFS(x + 1, val); }int main() {read(w); read(n);for(int i = 1; i <= n; ++i)read(a[i]);sort(a + 1, a + n + 1,cmp);dfs(1, 0);sort(b + 1, b + top + 1);c[++tot] = 0;for(int i = 1; i <= top; ++i) {if(b[i] != b[i - 1]) c[++tot] = b[i];}DFS(n / 2 + 3, 0);write(ans);return 0; }

 

转载于:https://www.cnblogs.com/AK-ls/p/11276734.html

总结

以上是生活随笔为你收集整理的送礼物（双向搜索）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。