題解

今天下午剛學了模擬退火

借這個題來總結下模擬退火的要注意的問題吧

1 : \(eps\)不要設的太大

2 : 初溫\(T\)在2000左右就差不多可以了

3 : 注意題目要求是要求最大值還是最小值,當x<0時\(exp(x)\)的取值范圍才是\(0~1\)

4 : 可以在退完火以后再單獨從當前最優答案下進行微調

5 : 可以進行多次退火

然后這題就是每次退火就是隨機交換序列中的兩個數,對序列DP一下就好了

題解

#include<ctime> #include<cmath> #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> const int M = 25 ; const int N = 8 ; const double INF = 1e50 ; const double EPS = 1e-3 ; using namespace std ;int n , m ; int val[M] , e[M] ; double f[N][M] , p[M] , Sum[M] ; double bax , Ans = INF ; inline double Rand() {return (double)((rand() % 101) / 100.0) ; } inline double F() {for(int i = 0 ; i <= m ; i ++)for(int j = 0 ; j <= n ; j ++) f[i][j] = INF ;f[0][0] = 0 ;for(int i = 1 ; i <= n ; i ++) Sum[i] = Sum[i - 1] + p[i] ;for(int i = 1 ; i <= m ; i ++)for(int j = i ; j <= n ; j ++)for(int k = i - 1 ; k < j ; k ++)f[i][j] = min(f[i][j] , f[i - 1][k] + (Sum[j] - Sum[k] - bax) * (Sum[j] - Sum[k] - bax)) ;if(f[m][n] < Ans) {Ans = f[m][n] ;for(int i = 1 ; i <= n ; i ++) e[i] = p[i] ;}return f[m][n] ; }inline void Solve() {for(int i = 1 ; i <= n ; i ++) p[i] = e[i] ;double T = 2000 , W = 0.98 ;double NowAns , PreAns , dlt ;while(T > EPS) {PreAns = F() ;int a = rand() % n + 1 , b = rand() % n + 1 ;while(a == b) b = rand() % n + 1 ;swap(p[a], p[b]) ;NowAns = F() ; dlt = NowAns - PreAns ;if(exp(-dlt / T) > Rand()) ;else swap(p[a] , p[b]) ;T *= W ;}for(int i = 1 ; i <= 10000 ; i ++) {int a = rand() % n + 1 , b = rand() % n + 1 ;while(a == b) b = rand() % n + 1 ;swap(p[a] , p[b]) ;F() ;swap(p[a] , p[b]) ;} } int main() {srand(time(0)) ;cin >> n >> m ;for(int i = 1 ; i <= n ; i ++) {cin >> val[i] ;bax += val[i] ;p[i] = val[i] ;}bax /= m ; F() ;int Times = 20 ; while(Times--) Solve() ;printf("%.2lf\n",sqrt(Ans / m)) ;return 0 ; }

轉載于:https://www.cnblogs.com/beretty/p/10071905.html

總結

以上是生活随笔為你收集整理的[HAOI2006]均分数据的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。