莫欺少年穷，修魔之旅在这开始—>算法提高课题解

双向DFS

思路：

1. 选择前 n / 2个物品，搞出它们的所有组合
2. 排除等效冗余：对 weights 数组进行排序去重，不过这个的必要性不大，因为后面有二分
3. 对后面 n / 2个物品做选择，搞出一个组合就取二分 weights 数组里面的符合条件的最大重量，然后更新 ans
4. 最优性剪枝：如果说 ans 已经达到了最大重量，那就没有必要再继续枚举后面的选择了

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 46;

int m,n;
int w[N];
int weights[1<<23];
int cnt,ans;

//把前 n / 2 个物品的所有选择打一个表
void dfs1(int u,int s)
{
    if(u==n/2) 
    {
        weights[cnt++]=s;
        return;
    }

    //不选这个物品
    dfs1(u+1,s);

    //选择这个物品
    if((LL)s+w[u]<=m) dfs1(u+1,s+w[u]);
}

//枚举后 n / 2 个物品的所有选择，看这个选择可以达到的最大重量
void dfs2(int u,int s)
{
    //如果说ans已经达到了最大重量，那就没有必要在继续枚举了
    if(ans==m) return;

    //枚举完了所有物品
    if(u==n)
    {
        //二分找与这个选择可以匹配的最大重量
        int l=0,r=cnt-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if((LL)weights[mid]+s<=m) l=mid;
            else r=mid-1;
        }

        //更新最大重量
        ans=max(ans,weights[l]+s);

        return;
    }

    //不选这个物品
    dfs2(u+1,s);

    //选择这个物品
    if((LL)s+w[u]<=m) dfs2(u+1,s+w[u]);
}

int main()
{
    cin>>m>>n;

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

    dfs1(0,0);

    //排序
    sort(weights,weights+cnt);

    //去重后的个数
    cnt=unique(weights,weights+cnt)-weights;

    dfs2(n/2,0);

    cout<<ans<<endl;

    return 0;
}