一维背包问题模拟退火.txt

背包问题得模拟退火解法实现

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <math.h>
#define N 9

double wi[]={1,2,3,4,5,6,7,8,9}; //物品重量weight
double vi[]={10,4,3,2,1,1,2,1,1};//物品体积
double ci[]={20,9,7,5,1,3,4,2,3}; //物品价值
double W=33; // 背包最大重量
double V=20; // 背包最大容量
void main()
{
	int x[N]; // 初始解	
	double c=0;  //当前价值
	double w=0;  //当前重量
	double v=0;  //当前体积
	long L=100*N; // Mapkob 链长
	int i,j,k;
	for(i=0;i<N;i++)
	{
		x[i]=0;//初始解全不放入
		c=c+ci[i]*x[i];
		w=w+wi[i]*x[i];
	}
	double	t0=500; // 控制参数t的初值 
	double	t=t0;
	double	tf=0.95; // 衰减函数的系数
	double dc,dw,f_max;
	srand( (unsigned)time( NULL ) );
	double e=0.00001;
	while (t>e)
	{
			for(i=0;i<N;i++)
			{
				cout<<x[i]<<",";
			}
			cout<<endl;
	   for(k=1;k<L;k++)
	   {

		   i=rand()*(N-1)/RAND_MAX; 
			if (x[i]==0 )//待放入
			{
				if (w+wi[i]<=W ) //未超重，直接放入
				{
					x[i]=1;
					c=c+ci[i];
					w=w+wi[i]; 
				//	cout<<"加入w"<<i<<endl;

				}
				else  //再加入i下标得物品要超重
				{
					j=rand()*(N-1)/RAND_MAX; 
				//	if
					while (x[j]==0  )
					{
						j=rand()*(N-1)/RAND_MAX; 
					}
					dc=ci[i]-ci[j];//
					dw=wi[i]-wi[j];
					if (w+dw<=W  )  //能够交换出下标为j得物品
					{ 
						if( (dc>0)||(exp(dc/t)>((double)rand()/RAND_MAX) ))// 接受准则
						{
							x[i]=1;
							x[j]=0;//放入i，取出j物品
							c=c+dc;
							w=w+dw;  
						//	cout<<"加入w"<<i<<"去掉w"<<j<<endl;
						}
					}
				}
			}
			else //i物品已经被放入
			{
				j=rand()*(N-1)/RAND_MAX;   
				while( x[j]==1)//换着放入j下标物体
					j=rand()*(N-1)/RAND_MAX; 
           		dc=ci[j]-ci[i];
				dw=wi[j]-wi[i];  
				if (w+dw<=W  )
				{
					if ((dc>0)||(exp(dc/t)>((double)rand()/RAND_MAX) ))
					{
							x[i]=0;
							x[j]=1;
							c=c+dc;
							w=w+dw;
						//	cout<<"加入w"<<j<<"去掉w"<<i<<endl;
					}
				}
			}
	   }
		t=t*tf; //衰减函数
		f_max=c;
	}
	cout<<"\n结果:";
	for(i=0;i<N;i++)
	{
		cout<<x[i]<<",";
	}
	cout<<endl;
	cout<<"最大价值:"<<f_max<<endl;

}