ch2401送礼物（双向dfs）

题意：给n个物品，以及背包的容量w，求最多能装下多少重量的物品。

题解：直接01背包存不下所以二分搜索

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
ll a[55],s[1<<25];
ll ans, n, w, tot;
void DFS1(ll x,ll v)
{
    if(x>n)
	{
        s[++tot]=v;
        return;
    }
    if(a[x]+v<=w)
        DFS1(x+1,a[x]+v);
    DFS1(x+1,v);
}
void DFS2(ll x, ll v)
{
    if(x>=(n+1)>>1)
	{
        ll l=lower_bound(s+1,s+tot+1,w-v)-(s+1);
        ans=max(ans,v+s[l]);
        return;
    }
    if(a[x]+v<=w)	DFS2(x+1,a[x]+v);
    DFS2(x+1,v);
}
int main()
{
	scanf("%d%d",&w,&n);
    for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    ll mid=(n+1)>>1;
	DFS1(mid,0);
    sort(s+1,s+tot+1);
	DFS2(1,0);
    printf("%d",ans);
    return 0;
}