双向深度优先搜索、斐波那契数列

由于从质量第 $3$ 小的砝码开始，每个砝码的质量至少等于质量比它小的砝码中质量最大的两个的质量的和且天平最大承重为 $2^{30}$，可以得知至多有 $44$ 个砝码，不考虑 $O(2^n)$ 的朴素搜索，考虑 $O(\sqrt{2^n})$ 的双向搜索。

先搜出前一部分可以获得的所有重量记为序列 $s$ 并排序，然后在搜索后一部分能够获得的重量时，若当前重量为 $sum$，则二分求出最大的满足 $s_i+sum \leq C$ 的 $s_i$ 并更新答案。

总体时间复杂度 $O(n \sqrt{2^n})$。

#include<bits/stdc++.h>
using namespace std;
int c,n,ans,cnt,a[50],s[5000005];
void dfs(int x,int lim,int sum,function<void(int)> fun){
    if(x>lim) return fun(sum);
    dfs(x+1,lim,sum,fun);
    if(1ll*sum+a[x]<=c) dfs(x+1,lim,sum+a[x],fun);
}
int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    if(n==1) return printf("%d\n",a[1]<=c ? a[1]:0),0;
    dfs(1,n/2,0,[&](int x)->void{s[++cnt]=x;});
    sort(s+1,s+cnt+1);
    dfs(n/2+1,n,0,[&](int x)->void{ans=max(ans,x+*(upper_bound(s+1,s+cnt+1,c-x)-1));});
    printf("%d\n",ans);
    return 0;
}