模拟退火求调
查看原帖
模拟退火求调
1014573
sevenki楼主2023/9/3 09:57

蒟蒻刚学模拟退火,只过了前面3个点,请大佬看看哪里有问题

#include <bits/stdc++.h>
#define MAXM 166
#define ll long long
using namespace std;
const double delta = 0.997;
const double eps = 1e-14;
int n,k;
bitset<MAXM> now;
int ans;
int v[MAXM],w[MAXM];
bool isRight(bitset<MAXM> x){
	int tmp = 0;
	for(int i=1;i<=n;i++){
		tmp+=x[i]*v[i];
	}
	return tmp<=k;
}
int calc(bitset<MAXM> x){
	int tmp = 0;
	for(int i=1;i<=n;i++){
		tmp+=x[i]*w[i];
	}
	return tmp;
}
void solve(){
	double t = 100000;
	bitset<MAXM> nowp;
	while(t>eps){
		bitset<MAXM> tmp=nowp;
		int rnd = rand()%n+1;
		tmp[rnd]= (tmp[rnd]) ? 0 : 1;
		if(!isRight(tmp))continue;
		if(calc(tmp)>ans){
			ans=calc(tmp);
			nowp=tmp;
		}else{
			if((double)rand()/RAND_MAX<=exp((calc(tmp)-ans)/t)){
				nowp=tmp;
			}
		}
		t*=delta;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	srand(time(nullptr));
	cin>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
	}
	while((double)clock()/CLOCKS_PER_SEC<=0.96)solve();
	cout<<ans;
	return 0;
}
2023/9/3 09:57
加载中...