dknap.cpp

动态规划0-1背包问题

//
//		DKNAP
//		使用动态规划求解0/1背包问题
//		kingwind
//		2003.12.1
///////////////////////////////////////////////////////

#include "DKNAP.h"

DKNAP::DKNAP(int n,int m,double M)
{
	m_n = n;
	m_M = M;

	m_P = new double[n];
	m_w = new double[n];	//用于存放读入的数据

	m_dP = new double[m];
	m_dW = new double[m];	//用于记录所有的Si分组数据

	m_F = new int[n+1];		//Si的分组指示
	m_X = new int[n];		//用于记录结果取值

	//几个记录数组的初始化代码
	for(int i = 0;i < n;i ++)
	{
		m_P[i] = 0;
		m_w[i] = 0;

		m_F[i] = 0;
	}	
	m_F[i] = 0;

	for(i = 0;i < m;i ++)
	{
		m_dP[i] = 0;
		m_dW[i] = 0;
	}
}

DKNAP::~DKNAP()
{
	delete[] this->m_P;
	delete[] this->m_w;
	delete[] this->m_dP;
	delete[] this->m_dW;
	delete[] this->m_F;
}

void DKNAP::readData()
{
	double tp[] = {3,3,5};
	double tw[] = {1,2,5};

	for(int i = 0; i < 3;i++)
	{
		this->m_P[i] = tp[i];
		this->m_w[i] = tw[i];
	}
	//以上数据仅供测试用
}

void DKNAP::handle()
{
	int l = 0;								//首指示变量
	int h = 0;								//尾指示变量
	int next = 0;							//用于指示Si分组下标
	int k = 0;
	int done = 1;
	double pp,ww;							//用于循环中的暂时存储

	this->m_F[0] = 0;						//指示S0
	this->m_dP[0] = 0;
	this->m_dW[0] = 0;						//S0

	next = 1;
	this->m_F[1] = next;					//指示S1的开始

	for(int i = 0;i < this->m_n-1;i ++)		//生成Si
	{
		k = l;
		
		for(int j = l;j <= h;j ++)			//在l-h中找到W[r]+w[i]<=M的最大的r
		{
			if(this->m_dW[j] + this->m_w[i] <= this->m_M)
				done = j;
			else
				break;
		}

		for(j = l;j <= done;j ++)			//生成Si1并归并
		{
			//Si1中的下一元素
			ww = this->m_dW[j] + this->m_w[i];
			pp = this->m_dP[j] + this->m_P[i];

			while((k <= h) && 
				(this->m_dW[k] < ww))		//从Si-1中取元素来归并
			{
				this->m_dP[next] = this->m_dP[k];
				this->m_dW[next] = this->m_dW[k];
				next ++;
				k ++;
			}

			if((k <= h) && (this->m_dW[k] == ww))
			{
				pp = (pp >= this->m_dP[k] ? pp:this->m_dP[k]);
				k ++;
			}

			if(pp > this->m_dP[next-1])
			{
				this->m_dP[next] = pp;
				this->m_dW[next] = ww;
				next ++;
			}

			while((k <= h) &&				//清除
				(this->m_dP[k] <= this->m_dP[next-1]))
			{
				k ++;
			}
		}

		//将Si-1中剩余的元素并入Si
		while(k <= h)
		{
			this->m_dP[next] = this->m_dP[k];
			this->m_dW[next] = this->m_dW[k];
			next ++;
			k ++;
		}

		l = h + 1;
		h = next - 1; 
		//cout<<endl<<"l="<<l<<"\th="<<h<<endl;//just for test
		this->m_F[i+2] = next;
	}

	//回溯，确定Xn,...,X2,X1的取值
    double px = m_dP[m_F[this->m_n]-1];
	double wx = m_dW[m_F[this->m_n]-1];
	double py,wy;
	int curXPos = this->m_n-1;				//用于指示已经回溯的解

	//cout<<px<<" "<<wx<<endl;//just for test
	int ll = this->m_F[this->m_n-1]+1;
	int hh = this->m_F[this->m_n]-1;

	//找最未序列中的最大满足解
	for(int kl=ll;kl<=hh;kl++)
	{
		if((this->m_dW[kl] + this->m_w[this->m_n-1]) <= this->m_M)
		{
			py = this->m_dP[kl] + this->m_P[this->m_n-1];
			wy = this->m_dW[kl] + this->m_w[this->m_n-1];
		}
		else 
			break;
	}

	if(px > py)
		this->m_X[curXPos] = 0;
	else
		this->m_X[curXPos] = 1;
	curXPos --;

	//cout<<"Test:"<<this->m_X[curXPos]<<endl;
	for(kl = this->m_n-1;kl > 0;kl --)
	{
		//py,wy记录着当前提有的(p,w)值
		py = py - this->m_P[kl]; 
		wy = wy - this->m_w[kl];
		//检查px,wx是否出现在前一个m_dW和m_dP记录中
		ll = this->m_F[kl-1];
		hh = this->m_F[kl]-1;

		int flag = 0;			//设检测标志位，记录Xi是否已置0
		for(int cl = ll;cl <= hh;cl ++)
		{
			if(this->m_dP[cl] == py && this->m_dW[cl] == wy)
			{
				this->m_X[curXPos] = 0;
				curXPos --;
				flag = 1;
			}
		}
		if(flag == 0)
		{
			this->m_X[curXPos] = 1;
			curXPos --;
		}
	}
	//处理X0的取值
	if(py != 0 && wy != 0)
		this->m_X[0] = 1;
	else
		this->m_X[0] =0;
}

void DKNAP::printResult()
{
	cout<<"Ai记录:"<<endl;
    
	for(int j = 0;j<this->m_n;j++)
	{	
		cout<<"A"<<j<<":";
		for(int i = this->m_F[j];i < this->m_F[j+1];i ++)		//将结果按照(p,w)格式输出 
		{
			cout<<"("<<(this->m_dP[i])<<","<<(this->m_dW[i])<<")\t";
		}
		cout<<endl;
	}
	cout<<endl<<"背包问题答案:"<<endl;
	for(j = 0;j< this->m_n;j++)
	{
		cout<<"X["<<j<<"] = "<<this->m_X[j]<<"\t";
	}
	cout<<endl<<endl;
}