bknap.cpp

回溯法解决0-1背包问题

//
//		背包问题	使用回溯算法求解
//		kingwind 
//		2003.12.10
////////////////////////////////////////////////

#include "BKNAP.h"

BKNAP::BKNAP(int n,double m)
{
	this->m_n = n;
	this->m_M = m;

	this->m_P = new double[n];
	this->m_W = new double[n];

	this->m_X = new int[n];
	this->m_Y = new int[n];
}

BKNAP::~BKNAP()
{
	delete[] this->m_P;
	delete[] this->m_W;
	delete[] this->m_X;
	delete[] this->m_Y;
}

void BKNAP::readData()
{
	double tp[] = {11,21,31,33,43,53,55,65};
	double tw[] = {1,11,21,23,33,43,45,55};

	for(int i=0;i<this->m_n;i++)
	{
		this->m_P[i] = tp[i];
		this->m_W[i] = tw[i];
	}
}

void BKNAP::handle()
{
	double cp = 0;		//当前重量
	double cw = 0;      //当前效益值

	int k = 0;
	this->m_fP = -1;
	
	while(true)
	{
		//将物体k放入背包
		while(k < this->m_n && cw+this->m_W[k] <= this->m_M)
		{
			cw += this->m_W[k];
			cp += this->m_P[k];
			
			this->m_Y[k] = 1;
			k ++;
		}

		if(k>=this->m_n)
		{
			this->m_fP = cp;
			this->m_fW = cw;
			k = this->m_n-1;
			change();//修改X的取值,使用Y
		}
		else		//超出M,物品K不适合
			this->m_Y[k] = 0;

		while(this->bound(cp,cw,k) <= this->m_fP)
		{
			while(k != -1 && this->m_Y[k] != 1)
				k --;//找最后放入背包的物品 
			
			if(k == -1)//算法在此处结束
			{
				this->displace();
				return;
			}

			this->m_Y[k] = 0;
			cw -= this->m_W[k];
			cp -= this->m_P[k];
		}
		k ++;

		if(k == this->m_n && (this->m_X[0] == 0 || this->m_X[0] == 1))
			this->displace();
	}
}

void BKNAP::displace()
{
	cout<<"背包问题的解是:"<<endl;
	for(int i = 0;i < this->m_n;i ++)
	{
		cout<<"X["<<i<<"] = "<<this->m_X[i]<<"\t";
	}
	cout<<endl;
}

//P：当前的效益总量；
//W：当前的背包重量；
//K：上次去掉的物品
double BKNAP::bound(double p,double w,int k)
{
	double b,c;

	b = p;
	c = w;

	for(int i = k+1;i<this->m_n;i++)
	{
		c += this->m_W[i];
		if(c < this->m_M)
		{
			b += this->m_P[i];
		}
		else
		{
			return (b + (1 + (c - this->m_M)/this->m_W[i]*this->m_P[i]));
		}
	}

	return b;
}

void BKNAP::change()
{
	for(int i = 0;i < this->m_n;i ++)
	{
		this->m_X[i] = this->m_Y[i];
	}
}