B26 双向DFS 送礼物

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N=1 << 24;
 
int n,k,cnt;
LL w[N],g[50],W,ans;
 
void dfs(int x, int s)
{
    if( x==k+1 ){w[++cnt]=s;return ;}
    
    if( s+g[x]<=W ) dfs(x+1,s+g[x]);
    dfs(x+1,s);
}
 
void dfs2(int x, int s)
{
    if( x==n+1 )
    {
        int l=1, r=cnt;
        while( l<r )
        {
            int mid=l+r+1>>1;
            if( w[mid]+s<=W ) l=mid;
            else r=mid-1;
        }
        if( w[l]+s<=W ) ans=max(ans,w[l]+s);
        return ;
    }
     
    if( s+g[x]<=W ) dfs2(x+1,s+g[x]);
    dfs2(x+1,s);
}
 
int main()
{
    scanf("%lld%d", &W, &n);
    for(int i=1; i<=n; i++) scanf("%lld", &g[i]);
    sort(g+1, g+n+1);reverse(g+1,g+n+1);
     
    k=n/2;cnt=0;
    dfs(1,0);
    
    sort(w+1, w+cnt+1);
    int t=0;for(int i=2;i<=cnt;i++)if(w[i]!=w[i-1])w[++t]=w[i];
    cnt=t;
    
    ans=0; 
    dfs2(k+1,0);
    
    printf("%d\n", ans);
    return 0;
}

B26 双向DFS 送礼物

#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N=1 << 24;
 
int n,k,cnt;
LL w[N],g[50],W,ans;
 
void dfs(int x, int s)
{
    if( x==k+1 ){w[++cnt]=s;return ;}
    
    if( s+g[x]<=W ) dfs(x+1,s+g[x]);
    dfs(x+1,s);
}
 
void dfs2(int x, int s)
{
    if( x==n+1 )
    {
        int l=1, r=cnt;
        while( l<r )
        {
            int mid=l+r+1>>1;
            if( w[mid]+s<=W ) l=mid;
            else r=mid-1;
        }
        if( w[l]+s<=W ) ans=max(ans,w[l]+s);
        return ;
    }
     
    if( s+g[x]<=W ) dfs2(x+1,s+g[x]);
    dfs2(x+1,s);
}
 
int main()
{
    scanf("%lld%d",&W, &n);
    for(int i=1; i<=n; i++) scanf("%lld",&g[i]);
    sort(g+1, g+n+1);reverse(g+1,g+n+1);
     
    k=n/2;cnt=0;
    dfs(1,0);
    sort(w+1, w+cnt+1);
    int t=0;for(int i=2;i<=cnt;i++)if(w[i]!=w[i-1])w[++t]=w[i];
    cnt=t;
    
    ans=0; 
    dfs2(k+1,0);
    
    printf("%d\n", ans);
    return 0;
}