怎样给网站做seo优化什么是搜索引擎优化seo

171. 送礼物 - AcWing题库

一个序列选若干个数，求不大于W的最大值

        对于前一半数，可以先DFS出所有可能的和储存到weight[]

        对于另一半数，通过DFS找出所有可能的和，并对每一个和，在weight[]二分查找与其之和不大于W的最大值即可

#include<iostream>
#include<algorithm>
using namespace std;
const int N=50;
typedef long long ll;
int w[N];
int n,m;
int k;
int weight[1<<25];
int cnt;
int ans;
//第u个数  和为s
void dfs1(int u,int s)
{if(u==k){weight[cnt++]=s;return;}dfs1(u+1,s);if((ll)s+w[u]<=m) dfs1(u+1,s+w[u]);}
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(weight[mid]<=m-s)l=mid;else r=mid-1;}ans=max(ans,weight[l]+s);return;}dfs2(u+1,s);if((ll)s+w[u]<=m) dfs2(u+1,s+w[u]); 
}
int main()
{cin>>m>>n;for(int i=0;i<n;i++) cin>>w[i];sort(w,w+n);reverse(w,w+n);k=n/2+2;dfs1(0,0);sort(weight,weight+cnt);cnt=unique(weight,weight+cnt)-weight; dfs2(k,0); cout<<ans<<endl;
}