退火求调
查看原帖
退火求调
260360
阿噫齐贝林楼主2022/9/1 18:06
#include<bits/stdc++.h>
using namespace std;
double f[50][50],a[50],d[50],fn,ans;
int n,m;
double suan()
{
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)
		d[i]=d[i-1]+a[i];	
	f[0][0]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			for(int k=1;k<=i;k++)
				f[i][j]=min(f[i][j],f[k-1][j-1]+(d[i]-d[k-1]-fn)*(d[i]-d[k-1]-fn));
	return sqrt(f[n][m]/m);
}
void SA()
{
	double T=1970;
	while(T>1e-15)
	{
		int x=rand()%n+1,y=rand()%n+1;
		swap(a[x],a[y]);
		double res=suan();
        double de=res-ans;
		if(de<0)ans=res;
		//exp(-de/t)*RAND_MAX>rand()
		else if(exp(-de/T)*RAND_MAX>rand())swap(a[x],a[y]);
		T*=0.989;
	}
}
int main()
{
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		fn+=a[i]/m;
	}
	ans=0x3f3f3f;
	for(int i=1;i<=5;i++)SA();
	printf("%.2lf",ans);
}

求求了

2022/9/1 18:06
加载中...