玄学算法——模拟退火

zibenlun · 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;
}