3sat 问题.cpp

对于给定的带权3-CNF

// 3SAT
#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
#include<time.h>

const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;

ofstream fos;              // 定义输出文件
int *value;

class RandomNumber
{
private:
	// 当前种子
	unsigned long randSeed;
public:
	// 构造函数，缺省值0表示由系统自动产生种子
	RandomNumber (unsigned long s=0);
	// 产生0:n-1之间的随机整数
	unsigned short Random (unsigned long n);
	// 产生[0,1)之间的随机实数
	double fRandom(void);
};

// 产生种子
RandomNumber::RandomNumber(unsigned long s)
{
	if (s==0)
		randSeed=time(0);   // 用系统时间产生种子
	else
		randSeed=s;
}

// 产生0:n-1之间的随机整数
unsigned short RandomNumber::Random(unsigned long n)
{
	randSeed=multiplier*randSeed+adder;
	return (unsigned short) ((randSeed>>16)%n);
}

// 产生[0,1)之间的随机实数
double RandomNumber::fRandom(void)
{
	return Random(maxshort)/double(maxshort);
}

RandomNumber rnd;
// 产生随机序列并计算权值和
int Sat(int **expression, int k, int m, int *&p)
{
	int *x=new int[k+1];
	for (int i=1;i<=k;i++)
	{
		x[i]=rnd.Random(2);
	}

	int sumtemp=0;
	for (i=1;i<=m;i++)
	{
		int j=1;
		while (j<=3)
		{
			int temp=expression[i][j];
			if (temp==0) break;
			if (temp>0)
			{
				if (x[temp]==1) { sumtemp+=value[i]; break; }
			}
			if (temp<0) 
			{
				if (x[-temp]==0) { sumtemp+=value[i]; break; }
			}
			j++;
		}
	}

	return(sumtemp);
}

void main()
{
	
	time_t start,end;
	start=clock();
	ifstream fis;              // 定义输入文件
    
	fis.open("input.txt");  //打开输入文件
	fos.open("output.txt");  //打开输入文件

	int k,m;

	fis>>k>>m;

	value=new int[m+1];

	int **expression=new int*[m+1];
	for(int i=0;i<=m;i++)
	    expression[i]=new int[4];

	int *single=new int[m+1];
	int num=0;
	
	// 处理输入
	for(i=1;i<=m;i++)
	{
		fis>>value[i];
		int j=0;
		int temp;
		fis>>temp;
		while (temp!=0)   
		{
			j++;
			expression[i][j]=temp;
			fis>>temp;
		}

		if (j==1) { num++;single[num]=expression[i][j]; }
		if (j!=3)  for (int s=j+1;s<=3;s++)  expression[i][s]=0;
	}

	int *p=new int[m+1];

	
	// 计算最大值上限
	int summax=0;
	for (i=1;i<=m;i++)   summax+=value[i];
	//fos<<summax<<endl;

	// 判断变量全为正或全为负
	bool positive=true,negetive=true;

	for (i=1;i<=m;i++)
	{
		int j=1;
		bool positivetemp=false;
		while(j<=3)
		{
			if (expression[i][j]>0)  { positivetemp=true; break; }
			j++;
		}
		if (positivetemp==false) { positive=false; break; }
	}

	for (i=1;i<=m;i++)
	{
		int j=1;
		bool negetivetemp=false;
		while(j<=3)
		{
			if (expression[i][j]<0)  { negetivetemp=true; break; }
			j++;
		}
		if (negetivetemp==false) { negetive=false; break; }
	}

	if (positive==true)  { fos<<summax<<endl; exit(1); }
	if (negetive==true)  { fos<<summax<<endl; exit(1); }

	// 处理输入均只有一个变量的情况
	if (num==m)
	{
		for (i=1;i<m;i++)
			for (int j=i+1;j<=m;j++)
				if (single[i]==-single[j])
				{
					if (value[i]>value[j]) summax-=value[j];
					else summax-=value[i];
				}
		fos<<summax<<endl;
		exit(1);
	}

	// 主程序
	int result=0;
	int *x=new int[k+1];

	//  次数控制
	int frequency;
	if ((k>0)&&(k<=75)) frequency=50000;
	if ((k>75)&&(k<=100)) frequency=80000;
	if ((k>100)&&(k<=500)) frequency=35000;
	if ((k>500)&&(k<=1000)) frequency=17000;
	if ((k>1000)&&(k<=5000)) frequency=3300;
	if (k>5000) frequency=1600;

	
	for(i=i;i<=frequency;i++) 
	{
		int sum=Sat(expression,k,m,p);
		if (sum==summax) { result=sum; }  
		if (sum>result) result=sum;
	}

	fos<<result<<endl;

	double t;
	end=clock();
	t=end-start;
	cout<<t<<endl;
}