knapsack4.cpp

这是经典的背包问题

#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
int n,c;
struct item
{
	int w,p;
};
vector<item> s;
class individual
{
#define MUT 8191
public:
	vector<int> x;
	int fitness,totw;
	individual()
	{
		int i,tmp;
		for(i=1;i<=n;i++)
		{
			tmp=rand()&1;
			x.push_back(tmp);
		}
	}
	void calf()
	{
		int i;
		fitness=0;
		for(i=0;i<n;i++)
		{
			fitness+=s[i].p*x[i];
		}
	}
	void drop()
	{
		int i;
		for(i=n-1;i>=0;i--)
		{
			if(totw<=c) break;
			if(x[i]==1)
			{
				x[i]=0;
				totw-=s[i].w;
			}
		}
	}
	void add()
	{
		int i;
		for(i=0;i<n;i++)
		if(x[i]==0&&totw+s[i].w<=c)
		{
			totw+=s[i].w;
			x[i]=1;
		}
	}
	void repair()
	{
		int i;
		totw=0;
		for(i=0;i<n;i++)
		{
			totw+=x[i]*s[i].w;
		}
		drop();
		add();
	}
	individual operator*(individual& tmp)
	{
		int i,r;
		individual chd;
		for(i=0;i<n;i++)
		{
			r=rand()&1;
			if(r) chd.x.push_back(x[i]);
			else chd.x.push_back(tmp.x[i]);
		}
		r=rand()&MUT;
		if(r<n)
		{
			chd.x[r]=1-chd.x[r];
		}
		chd.repair();
		chd.calf();
		return chd;
	}
};

class group
{
#define N 100
#define M 50000
#define T 2

public:
	individual u1,u2,v1,v2;
	individual mem[N+10];
	
	static bool cmp(const individual &a, const individual &b)
	{
		return a.fitness>b.fitness;
	}
	group()
	{
        int i;
        for(i=1;i<=N;i++)
        {
            mem[i].repair();
            mem[i].calf();
        }
		sort(mem+1,mem+N+1,cmp);
	}
	bool find(individual& a)
	{
		int i,j;
		bool found=false;
		for(i=1;i<=N;i++)
		if(mem[i].fitness==a.fitness)
		{
			found=true;
			for(j=0;j<n;j++)
			if(mem[i].x[j]!=a.x[j])
			{
				found=false;
				break;
			}
			if(found) break;
		}
		return found;
	}
	void insert(individual& a)
	{
		int i,j;
		if(!find(a))
		{
			mem[N+1]=a;
			i=N+1;
			while(i!=1)
			{
				j=i/2;
				if(mem[i].fitness>mem[j].fitness)
				{
					swap(mem[i],mem[j]);
					i=j;
				}
				else break;
			}
		}
	}
	void choose()
	{
		int i;
		u1=mem[rand()%N+1];
		v1=mem[rand()%N+1];
		for(i=2;i<=T;i++)
		{
			u2=mem[rand()%N+1];
			v2=mem[rand()%N+1];
			if(cmp(u2,u1))
			{
				u1=u2;
			}
			if(cmp(v2,v1))
			{
				v1=v2;
			}
		}
	}
	void crossover()
	{
		int i;
		individual chd;
		for(i=0;i<M;i++)
		{
            //showbest();
			choose();
			chd=u1*v1;
			insert(chd);
		}
	}
	void showbest()
	{
		int i;
		cout<<"profit = "<<mem[1].fitness<<endl;
		cout<<"x_code = ";
		for(i=0;i<n;i++)
		{
			cout<<mem[1].x[i];
		}
		cout<<endl;
	}
};

int main()
{
	int i;
	item tmp;
	freopen("input5.txt","r",stdin);
	cin>>n>>c;
	for(i=0;i<n;i++)
	{
		cin>>tmp.w>>tmp.p;
		s.push_back(tmp);
	}
	group G;
	G.crossover();
	G.showbest();
	while(1);
	return 0;
}