acwing171. 送礼物

题目

题解

数据最多有46个，简单使用爆搜会超时，可以先搜索前半段，将其结果保存下来，然后再对后半段进行搜索，从而将时间复杂度减小。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,w,ans,cnt,k;
int g[50],weights[1<<24];
//搜索前k个数据
void dfs(int u,int s){
    if(u==k){
        weights[cnt++]=s;//保存重量
        return;
    }
   if((LL)s+g[u]<=w)dfs(u+1,s+g[u]);
   dfs(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)weights[mid]+s<=w)l=mid;
            else r=mid-1;
        }
        if(weights[l]+(LL)s<=w)ans=max(ans,weights[l]+s);
        return;
    }
    if((LL)s+g[u]<=w)dfs2(u+1,s+g[u]);
    dfs2(u+1,s);
}
int main(){
    cin>>w>>n;
    for(int i=0;i<n;i++){
        cin>>g[i];
    }
    sort(g,g+n);
    reverse(g,g+n);
    k=n/2;
    dfs(0,0);
    sort(weights,weights+cnt);
    int t=1;
    for(int i=1;i<cnt;i++){
        if(weights[i]!=weights[i-1]){
            weights[t++]=weights[i];
        }
    }
    cnt =t;
    dfs2(k,0);
    
    cout<<ans<<endl;
    
    
    return 0;
}