upc7834 送礼物

题目描述

作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1)以下的任意多个物品。GY希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

输入

第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i],G[i]<= 2^31-1。

输出

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

样例输入

样例输出

提示

对于20%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1

最多45件礼物，如果直接暴力枚举就会超时。将礼物分成两半，分别枚举出两半中的各种组合，然后利用二分进行匹配，寻找最优解。

#include "bits/stdc++.h"

using namespace std;
const int maxn = 1e7 + 11;
typedef long long ll;
ll s[100];
ll sum[maxn];
ll ans = 0;
int tot = 0;
ll w, n;

void dfs1(int now, ll val) {
    if (now > n) {
        sum[++tot] = val;
        return;
    }
    if (val + s[now] <= w)
        dfs1(now + 1, val + s[now]);
    dfs1(now + 1, val);
}

int mid;

void dfs2(int now, ll val) {
    if (now >= mid) {
        ll l = lower_bound(sum + 1, sum + tot + 1, w - val) - sum;
        ans = max(ans, val + sum[l-1]);
        return;
    }
    if (val + s[now] <= w) dfs2(now + 1, val + s[now]);
    dfs2(now + 1, val);
}

int main() {
    //freopen("input.txt", "r", stdin);
    cin >> w >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    sort(s + 1, s + 1 + n);
    mid = (n + 1) >> 1;
    dfs1(mid, 0);
    sort(sum + 1, sum + tot + 1);
    dfs2(1, 0);
    cout << ans << endl;
    return 0;
}