elementalloc.cpp

用元素分配法求解0-1整数规划问题

// ElementAlloc.cpp: implementation of the CElementAlloc class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "..\..\INCLUDE\ElementAlloc.h"
#include "..\..\INCLUDE\TianjiDataType.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CElementAlloc::CElementAlloc()
{

}

CElementAlloc::~CElementAlloc()
{

}

/****************************求检验数函数，未加入对异常值的处理**************************************/
void CElementAlloc::ReckonVerify(int nWorkNum, int nWorkerNum, double* ptValue, int* ptVerify)
{
	int i = 0, j = 0, k = 0, l = 0;
	for(i = 0; i < nWorkerNum; i++)
	{
		for(j = 0; j < nWorkNum; j++)
		{
			int ndx = 0;
			for(l = (-1) * i; l < nWorkerNum - i; l++)
			{
				if(l)
				{
					for(k = (-1) * j; k < nWorkNum - j; k++)
					{
						/*************求每个元素的检验数************/
						if(k && (ptValue[i * nWorkNum + j] + ptValue[(i + l) * nWorkNum + j + k] 
							- ptValue[i * nWorkNum + j + k] - ptValue[(i + l) * nWorkNum + j] < 0))
							ndx++;
					}
				}
			}
			ptVerify[i * nWorkNum + j] = ndx;
		}
	}
}

/************************************根据检验数求指派问题的解********************************************************/
void CElementAlloc::ElementAlloc(int nWorkNum, int nWorkerNum,double* ptValue, struct ALLOCPROJECT* ptAllocProject)
{
	int i = 0, j = 0, nProjectNum = 0, nTemp = 0;
	double ftTemp = 1000.0;
	int* ptVerify = new int[nWorkNum * nWorkerNum];

	ReckonVerify(nWorkNum, nWorkerNum, ptValue, ptVerify);

	nProjectNum = nWorkNum;
	if(nWorkNum > nWorkerNum)nProjectNum = nWorkerNum;
	for(int k = 0; k < nProjectNum; k++)
	{
		nTemp = 0;
		ftTemp = 1000.0;
		for(i = 0; i < nWorkerNum; i++)
		{
			for(j = 0; j < nWorkNum; j++)
			{
				if(nTemp <= ptVerify[i * nWorkNum + j])nTemp = ptVerify[i * nWorkNum + j]; //找出值最大的检验数
			}
		}
		for(i = 0; i < nWorkerNum; i++)
		{
			for(j = 0; j < nWorkNum; j++)
			{
				if(nTemp == ptVerify[i * nWorkNum + j])
				{
					//若有多个同时为最大的检验数，则选择消费值最小的
					if(ftTemp > ptValue[i * nWorkNum + j])
					{
						ptAllocProject[k].nWorkNO = j;
						ptAllocProject[k].nWorkerNO = i;
						ftTemp = ptValue[i * nWorkNum + j];
					}
				}
			}
		}
		/***********************将找出的检验数对应的行和列划去************************/
		for(i = 0; i < nWorkerNum; i++)
			ptVerify[i * nWorkNum + ptAllocProject[k].nWorkNO] = -1;
		for(j = 0; j < nWorkNum; j++)
			ptVerify[ptAllocProject[k].nWorkerNO * nWorkNum + j] = -1;
	}
	delete []ptVerify;

}