思路：

1.

这 题 不卡常过不去啊……

（先加一个random_shuffle）

首先 我们可以折半 搜这一半可以到达的重量 sort一遍

然后搜另一半 对于路程中每一个解 我们可以二分前一半中加这个解最接近w的值，更新ans

剪枝：

对于第一次搜索 显然的剪枝：和不能大于w

对于第二次搜索 如果当前的解小于最大的remain 退出

我的搜索纯凭运气&数据…… 数据和w相差比较小就能过。

2.

LH大爷的思路（可惜T了…）（这题不卡数据是人？）

也是折半

然后二进制枚举每个选不选

s[i]表示

对于每个i s[i^ (1<< lowbit(i))]的值肯定是已知的。

s[i]=s[(i xor (1<<(f[i]-1)))]+a[f[i]]

sort一遍s

后面枚举 同理 二分同上…

然而t了。。

（感谢lydrainbowcat&LH大爷……）

//By SiriusRen

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

unsigned int n,w,a[66],half,maxx,ans=0x3fffffff;

unsigned int s[20000000],top;

inline void dfs(int x,int remain){

    s[top++]=remain;

    for(int i=x;i>=1;i--){

        int t=remain-a[i];

        if(t>=0)dfs(i-1,t);

    }

}

inline void dfs2(int x,int tot){

    if(s[top]>=tot){

        int t=lower_bound(s,s+top,tot)-s,jy=s[t]-tot;

        if(ans>jy)ans=jy;

        for(int i=x;i>=half;i--)

            dfs2(i-1,tot+a[i]);

    }

}

int main(){

    scanf("%d%d",&w,&n);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    half=(n+1)/2;

    random_shuffle(a+1,a+1+n);

    dfs(half,w);

    sort(s,s+top);

    half++;top--;

    dfs2(n,0);

    cout<<w-ans;

}