题目链接：传送门
描述
作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1)以下的任意多个物品。GY希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i],G[i]<= 2^31-1。
输出格式
仅一个整数，表示GY在他的力气范围内一次性能搬动的最大重量。
样例输入
20 5 7 5 4 18 1
样例输出
19
数据范围与约定
- 对于20%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1
题解：
如果直接暴搜，时间复杂度 $O(2^N)$ 原地起爆，可以使用折半DFS。
礼物分成两半，前一半 $O(2^{N/2})$ 的暴搜每个礼物选不选，然后把每种方案的重量之和存到数组 $S$ 里，并且排序、去重，以备后用。
再对后一半礼物进行 $O(2^{N/2})$ 暴搜，每种方案得到了重量后，去前面 $S$ 里二分找两个重量和加起来最大，且不超过 $W$ 的那个 $S[i]$。
优化后的时间复杂度是 $O(2^{N/2} cdot log 2^{N/2}) = O(N cdot sqrt{2}^N)$。
原本想用状压，发现应该是被卡了，因为状态转成重量还要凭空再多 $O(N)$ 的复杂度，比较尴尬……以后码代码前得记得先算算复杂度……别拿个假算法死怼半天……
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=50; int n,x; ll w,g[maxn]; int tot; ll S[1<<(maxn>>1)]; void dfs(int p,ll sum) { if(sum>w) return; if(p>x) { S[++tot]=sum; return; } dfs(p+1,sum); dfs(p+1,sum+g[p]); } ll ans; ll srch(ll x) { int l=1, r=tot; while(l<r) { int mid=(l+r+1)>>1; if(S[mid]<=x) l=mid; else r=mid-1; } return S[l]; } void dfs2(int p,ll sum) { if(sum>w) return; if(p>n) { ans=max(ans,sum+srch(w-sum)); return; } dfs2(p+1,sum); dfs2(p+1,sum+g[p]); } int main() { cin>>w>>n, x=(n+1)/2; for(int i=1;i<=n;i++) scanf("%d",&g[i]); sort(g+1,g+n+1,greater<int>()); tot=0; dfs(1,0LL); sort(S+1,S+tot+1); tot=unique(S+1,S+tot+1)-(S+1); ans=0; dfs2(x+1,0LL); cout<<ans<<endl; }