AcWing171.送礼物

题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

$1\le N\le 46$
$1\le W,G[i]\le 2^{31}-1$

输入样例

20 5
7
5
4
18
1

输出样例

19

思路

由于取得方法有$2^{46}$（70368744177664）种，肯定超时。但如果将其分成两组，每组就只有$2^{23}$（8388608）种，这就可以过了。先将第一组可能组成的数存入数组（要去重，不然TLE），然后再枚举第二组，枚举到一个数就二分搜索与第一组可以组成最大的数。

代码

#include <iostream>
#include <algorithm>
using namespace std;int n, w, k;
int a[50];
int pp[16777216], p[16777216], cnt, cnt1, ans;bool cmp(int x, int y)
{return x > y;
}void dfs1(int step, int last) 
{if (step == n / 2) {pp[cnt++] = last;return;}if ((long) last + a[step] <= w) dfs1(step + 1, last + a[step]);dfs1(step + 1, last);
}void dfs2 (int step, int last) 
{if (step == n) {int l = 0, r = cnt - 1;while(l < r) {int mid = (l + r + 1) / 2;if ((long) p[mid] + last <= w) l = mid;else r = mid - 1;}if ((long) p[l] + last <= w) ans = max(ans, p[l] + last);return;}if ((long) last + a[step] <= w) dfs2(step + 1, last + a[step]);dfs2(step + 1, last);
}int main() {cin >> w >> n;for (int i = 0; i < n; i++) cin >> a[i];sort(a, a + n, cmp);k = n / 2;dfs1(0, 0);sort(pp, pp + cnt);int cnt1 = cnt;cnt = 0;for (int i = 1; i <= cnt1; i++){if (pp[i] != pp[i - 1]) p[++cnt] = pp[i];}dfs2(n / 2, 0);cout << ans << endl;return 0;
}