DP复杂度是NV,本题中体积太大,显然不可以,所以只能搜索(本题目n很小),复杂度为$2^N$,N为45,显然也是超时的,进而想到双向搜索+二分
复杂度为$2^{N/2}$(搜索)* $\log{2^{N/2}}$(二分)
#include<bits/stdc++.h>
using namespace std;
const int N=1<<24,M=50;
typedef long long ll;
int n,m,k;
int g[M],weight[N];
int ans;
int cnt;
void dfs1(int u,int s){
if(u==k){
weight[cnt++]=s;
return;
}
if((ll)s+g[u]<=m) dfs1(u+1,s+g[u]);
dfs1(u+1,s);
}
void dfs2(int u,int s){
if(u==n){
int l=0,r=cnt-1; //二分答案
while(l<r){
int mid=l+r+1>>1;
if((ll)weight[mid]+s<=m) l=mid;
else r=mid-1;
}
if((ll)s+weight[l]<=m) ans=max(ans,weight[l]+s);
return;
}
if((ll)s+g[u]<=m) dfs2(u+1,s+g[u]);
dfs2(u+1,s);
}
int main(){
cin>>m>>n;
for(int i=0;i<n;i++) cin>>g[i];
sort(g,g+n); //优化搜索顺序
reverse(g,g+n);
k=(n/2)+1;
dfs1(0,0);
sort(weight,weight+cnt);
cnt=unique(weight,weight+cnt)-weight; //去重
dfs2(k,0);
cout<<ans<<endl;
}
二分时是不是应该 if((ll)weight[mid]+s<m) 或 if((ll)weight[mid]<m-s)
感觉<=就满足要求的,不一定要<
明白了,谢谢哈。