一：个人认为这道题的算法名字应该叫折半搜索

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 50;

int w[N], wei[1 << 25], cnt;
int n, m;
int ans;

void dfs1(int u, int sum, int ed){
    if(u >= ed){
        wei[cnt++] = sum;
        return;
    }
    if((long)sum+w[u] <= m)
        dfs1(u+1, sum+w[u], ed);
    dfs1(u+1, sum, ed);
}

void dfs2(int u, int sum, int ed){
    if(u >= ed){
        int k = m - sum;
        int l = 0, r = cnt - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;    
            if(wei[mid] <= k) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, wei[l] + sum);
        return;
    }
    if((long)sum+w[u] <= m)
        dfs2(u+1, sum+w[u], ed);
    dfs2(u+1, sum, ed);
}

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

    sort(w, w+n);
    reverse(w, w+n);//从大到小为了减小搜索空间

    dfs1(0, 0, n/2);//先搜索一半

    sort(wei, wei+cnt);
    cnt = unique(wei, wei + cnt) - wei;//去重

    dfs2(n/2, 0, n);//再搜另一半，二分的查找第一半中和第二半组合在一起的最大价值

    cout << ans << endl;    

}