本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-06 10:56:50

一定要通过啊！

歪解

看到题解里都是折半（或叫双端）搜索，那我就来发一个随便乱搞 模拟退火。

考场利器

模拟退火

由于我们不知道选几个数，所以直接暴力出选择的长度，再来跑上几遍 SA。

#include<bits\/stdc++.h>
using namespace std;
int n,m;
long long a[1000005];
long long ans;
long long check(int len){
	long long cnt=0;
	for(int i=1;i<=len;i++){
		cnt+=a[i];
	}
	if(cnt<=m) return cnt;
	else return 0;
}
void SA(int len){
	double t=rand()%6000,x=0.682755;
	while(t>1e-15){
		int l=rand()%(len)+1,r=min(rand()%(n-len+1)+len,n);
		swap(a[l],a[r]);
		long long sum=check(len);
		if(sum>ans){
			ans=sum;
		}
		else {
			if(rand()*pow(x,100)>t) swap(a[l],a[r]);
		}
		t*=x;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=10000;j++) SA(i);
	}
	cout<<ans;
	return 0;
}

正解

没什么讲的必要，纯纯模版题，双端搜完再二分拼合就行了。

#include<bits\/stdc++.h>
using namespace std;
long long a[1100005],b[1100005],s[55],ans,m,cntt,cnt,n;
void dfs1(int x,long long sum){
	if(sum>m) return;
	if(x>n\/2){
		a[++cnt]=sum;
		return;
	}
	dfs1(x+1,sum+s[x]);
	dfs1(x+1,sum);
}
void dfs2(int x,long long sum){
	if(sum>m) return;
	if(x>n){
		b[++cntt]=sum;
		return;
	}
	dfs2(x+1,sum+s[x]);
	dfs2(x+1,sum);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>s[i];
	dfs1(1,0);
	dfs2(n\/2+1,0);
	sort(a+1,a+cnt+1);
	sort(b+1,b+cntt+1);
	for(int i=1;i<=cnt;i++) ans=max(ans,b[upper_bound(b+1,b+cntt+1,m-a[i])-b-1]+a[i]);
	cout<<ans;
	return 0;
}