代码 折半搜索

#include<bits/stdc++.h>
using namespace std; 
#define LL long long  
const int N = 50 ; 
int n,w,a[N];
int ans;
vector<int> all;   
void dfs(int res,int mx,int nw,bool f)
{ 
	if(!f) all.push_back(res); 
	if(f)
	{ 
		int t=upper_bound(all.begin(),all.end(),w-res)-all.begin();
		if(all[t-1]+(LL)res<=w) ans=max(all[t-1]+res,ans); 
	}
	if(nw==mx+1) return ;
	if((LL)res+a[nw]<=w) dfs((LL)res+a[nw],mx,nw+1,f);
	dfs(res,mx,nw+1,f);
}
signed main()
{   
	scanf("%d%d",&w,&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		if(a[i]>w) i--,n--;
	}
	dfs(0,n/2 , 1    ,0);  
	sort(all.begin(),all.end()); 
	all.erase(unique(all.begin(),all.end()),all.end());//去重 删除重复元素; 
	dfs(0,n   , n/2+1,1);  
	printf("%d\n",ans);
}