详细请查看注释

参考代码：

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

using namespace std;

const int N = 46;

// 0也是一种情况，cnt 从1开始
int n, m, k, res, cnt = 1;
int w[N], ww[1 << 25];

/*
    2^46种选择!直接搜索直接TLE！
    使用背包也会因为O(nv) = 46 * 2^31 TLE！

    因此使用双向DFS，一半搜索2^25打表存储，一半搜索2^21（左右均衡一，前一半多一点）
    时间复杂度：2^25 * log2^25 = 8e8
*/

// 当前数编号 当前和
void dfs1(int u, int s){
    if(u == k){
        ww[cnt ++] = s;
        return;
    }
    // 不选 选
    dfs1(u + 1, s);
    if(1ll * s + w[u] <= m) dfs1(u + 1, s + w[u]);
}

// 当前数编号 当前和
void dfs2(int u, int s){
    if(u == n){
        // 二分找出小于m - s的最大值
        int l = 0, r = cnt - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(ww[mid] <= m - s) l = mid;
            else r = mid - 1;
        }
        res = max(res, s + ww[r]);
        return;
    }
    // 不选 选
    dfs2(u + 1, s);
    if(1ll * 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];

    // 搜索顺序优化，从大到小搜索
    sort(w, w + n, greater<int>());

    // 一搜：打表处理前一半
    k = n / 2 + 2;
    dfs1(0, 0);

    // 排序 + 去重
    sort(ww, ww + cnt);
    // 返回去重后的个数
    cnt = unique(ww, ww + cnt) - ww;

    // 二搜：处理后一半
    dfs2(k, 0);
    cout << res << endl;
    return 0;
}