040320173.cpp

著名的3SAT问题 用蒙特卡罗算法实现的！

#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <time.h>
void main()
{   clock_t start,end;
    start = clock();
	int maxweight = 0;//最终结果：最大权植
	int maxvalue = 0;//最大的可能权植：把所有权植全部相加
	int m,k;
    ifstream input("input.txt");
	input>>k>>m;
    int* weight=new int[m];//保存权植
	int* vary=new int[k];  //保存各个变量的植：0或1；
	int** a=new int*[m];   //保存各个表达式的变量下标；
  for(int i=0;i<m;i++)
    a[i]=new int[3];
  for(i=0;i<m;i++)
  {
	input>>weight[i];
	int temp;
	int j = -1;
	do{
	  input>>temp;
	  j++;
	  a[i][j] = temp;
	}while(temp!=0);
	if(j<2) for(int s=j;s<3;s++) a[i][s] = 0;
  }
  for(i=0;i<m;i++) maxvalue += weight[i];
	srand((unsigned)time(NULL));
	do{
		for(i=0;i<k;i++) 
		{
		  int boolvar = rand()%2;
		  vary[i] = boolvar;
		}
	   int tempmaxweight = 0;
	   for(i=0;i<m;i++)
	   {
	    for(int j=0;j<3;j++)
		{
		 if(a[i][j]==0) break;
		 if((a[i][j]>0)&&(vary[a[i][j]-1]==1)) {tempmaxweight += weight[i]; break;}
		 if((a[i][j]<0)&&(vary[abs(a[i][j])-1]==0)) {tempmaxweight += weight[i];break;}
		}
	   }
	   if(tempmaxweight>maxweight) maxweight = tempmaxweight;
	   if(maxweight==maxvalue) break;
       end = clock();
	}while(end-start<1000);
  ofstream output("output.txt");
  output<<maxweight; 
}