题目描述

达达帮翰翰给女生送礼物，翰翰一共准备了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

算法:双向dfs 时间复杂度$O(2^{n/2+1} + 2^{n/2-1} * log(2^{n/2+1}))$

双向dfs就好了，第一个dfs先打个表，第二个dfs找表中<= w最大的那个数就好了~。~
ps:vector过不去！！！,题目的数据有点狠。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 50;

int w[N],n,v,k;

int a[1<<25],cnt=1;

int res;

int get(int x)
{
    int l=0,r=cnt-1;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(a[mid]>x) r=mid-1;
        else l=mid;
    }
    return r;
}

void dfs1(int u,int s)
{
    if(u==k)
    {
        a[cnt++]=s;
        return ;
    }

    if(0ll + s + w[u] <= v)
        dfs1(u+1,s+w[u]);

    dfs1(u+1,s);
}

void dfs2(int u,int s)
{
    if(u==n)
    {
        int x=v-s;
        res=max(res,s+a[get(x)]);
        return ;
    }

    dfs2(u+1,s);
    if(0ll + s + w[u] <=v)
        dfs2(u+1,s+w[u]);
}

int main(){

    cin >> v >> n;

    for(int i=0;i<n;i++)
        cin >> w[i];

    k = n/2 + 1;

    dfs1(0,0);

    sort(a,a+cnt);

    cnt = unique(a,a+cnt) - a;

    dfs2(k,0);

    cout << res << endl;

    return 0;
}