coinshandler.cpp

使用贪心技术

// CoinsHandler.cpp: implementation of the CCoinsHandler class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "SmallChage.h"
#include "CoinsHandler.h"
#include "Setting.h"
#include "Coin.h"
#include "CostomizedTypes.h"
#include <fstream>

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

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

CCoinsHandler::CCoinsHandler()
{
	m_nMoney = 0;
	m_nCoinsTypes = 0;
	m_MinimumCoinsNum = 0;
}

CCoinsHandler::~CCoinsHandler()
{
	CCoin* pCoin;
	int nIndex, Size;

	Size = m_pArrCoins.GetSize();
	for (nIndex = 0; nIndex < Size; nIndex++)
	{
		pCoin = (CCoin*)m_pArrCoins[nIndex];
		delete pCoin;
	}
	m_pArrCoins.RemoveAll();
}

int CCoinsHandler::GetMoney() const
{
	return m_nMoney;
}

int CCoinsHandler::GetMinimumCoinsNum() const
{
	return m_MinimumCoinsNum;
}

int CCoinsHandler::GetCoinsTypes() const
{
	return m_nCoinsTypes + 1;
}

VOID CCoinsHandler::Initialization()
{
	int nRet = m_SettingDlg.DoModal();
	if (IDCANCEL == nRet)
	{
		m_nMoney = *m_SettingDlg.m_pMoney;
		m_Strategy = *m_SettingDlg.m_pStrategy;
		m_pArrCoins.Copy(m_SettingDlg.m_ptrCoins);
		m_nCoinsTypes = m_pArrCoins.GetSize();
	}
}

BOOL CCoinsHandler::GetSolution(Strategy stratey)
{
	BOOL bRet = FALSE;
	switch (stratey)
	{
	case S_PROGRAMMING:
		bRet = ProgramingStrategy();		
		break;
	case S_GREEDY:
		bRet = GreedyStrategy();
		break;
	default:
		break;
	}
	return bRet;
}

VOID CCoinsHandler::SortByFacevalue(BOOL bAcs /* = TRUE */)
//直接选择排序，时间复杂度O(n^2)，不稳定排序
{
	// 	ofstream out("add.txt");
	//	out<<"before sort"<<endl;
	// 	for (int b = 0; b < m_ptrCoins.GetSize(); b++)
	// 		out<<m_ptrCoins.GetAt(b)<<'	';
	
	int k;
	int mVal, Val;
	CCoin *mPtr,*Ptr;
	int nSize = m_pArrCoins.GetSize();
	for (int i = 0; i < nSize; i++)
	{
		k = i;
		mPtr = (CCoin*)m_pArrCoins.GetAt(i);
		mVal = mPtr->GetFaceValue();
		for (int j = i + 1; j < nSize; j++)
		{
			Ptr = (CCoin*)m_pArrCoins.GetAt(j);
			Val = Ptr->GetFaceValue();
			if (mVal > Val && bAcs)								//升序排序
			{
				mVal = Val;
				mPtr = Ptr;
				k = j;
			}
			else if (mVal < Val && !bAcs)						//降序排序
			{
				mVal = Val;
				mPtr = Ptr;
				k = j;
			}										
		}
		if (k != i)												//交换地址
		{
			m_pArrCoins.SetAt(k,m_pArrCoins.GetAt(i));
			m_pArrCoins.SetAt(i,mPtr);
		}
	}
	// 	out<<endl<<"after sort:"<<endl;
	// 	for (int c = 0; c < m_ptrCoins.GetSize(); c++)
	// 		out<<m_ptrCoins.GetAt(c)<<'	';
}

BOOL CCoinsHandler::ProgramingStrategy()
//////////////////////////////////////////////////////////////////////////
//
//def:设Vi为第i种硬币的面值，且Vi<V(i+1)，其中i=1..n-1；
//	  M[i][j]是可找出钱数j的最少硬币个数；
//	  则M[n][m]，即n种按面值升序排序的硬币，能够找钱m的最少硬币个数。
//							min{M[i-1][j], k + M[i-1][j- k * Vi]},	j - k*Vi ≥ 0
//存在递归关系：M[i][j] = ｛															（1）
//							M[i-1][j]							 ,	j - Vi ＜ 0
//
//				当 j ≥ 1 时，M[0][j] = +∞; 当 i ≥ 0 时，M[i][0] = 0;					（2）
//
//********************************************************
//注：①多组最优解存在时，此算法只能求得一组 [10/19/2008]*
//	  ②Vi受正整数条件限制								 *
//	  ③时间复杂性为 O(nc)，当c>2^n时，算法可以改进		 *
//	  ④算法的空间复杂性是否可以降低？？？				 *
//********************************************************
//////////////////////////////////////////////////////////////////////////
{
	BOOL bRet = FALSE;
	SortByFacevalue();				////按面值排序

	VVI M;							//定义整型二维向量组存放M[i][j]
	VVI K;							//保存最优解
	M.resize(m_nCoinsTypes + 1);
	K.resize(m_nCoinsTypes + 1);

	int i,j;						//用于循环
	int Vi;							//第i种硬币的面值
	int Ni;							//第i种硬币的可用数量
	int	k;							//第i种硬币最多可使用的数量

	for (i = 0; i <= m_nCoinsTypes; i++)
	{
		M[i].resize(m_nMoney + 1);
		K[i].resize(m_nMoney + 1);
		for (j = 0; j <= m_nMoney; j++)
		{
			K[i][j] = 0;

			if (i == 0)
			{
				if (j != 0)
					M[i][j] = PLUSINFINITE;
				else
					M[i][j] = 0;
			}
		}
	}

	for (i = 1; i <= m_nCoinsTypes; i++)
	{
		Vi = ((CCoin*)m_pArrCoins.GetAt(i - 1))->GetFaceValue();
		for (j = 1; j <= m_nMoney; j++)
		{
			if (j < Vi)
				M[i][j] = M[i - 1][j];
			else
			{
				k = j / Vi;	
				K[i][j] = k;
				M[i][j] = min(M[i - 1][j], M[i - 1][j - k * Vi] + k);
			}
		}
	}

 	ofstream out("ProgramingSolution.txt");
	j = m_nMoney;
	CCoin* pCoin;
	for (i = m_nCoinsTypes; i > 0; i--)
	{
		pCoin = (CCoin*)m_pArrCoins.GetAt(i - 1);
		Vi = pCoin->GetFaceValue();
		Ni = pCoin->GetAvailableNum();
		if (j > 0 && K[i][j])
		{
			k = min(Ni,K[i][j]);										//硬币i的数目不一定是充足的
			j -= k * Vi;
			pCoin->UseCoins(k);											//使用k个该面值的硬币
		}
	}

	if (j == 0)															//要找的钱数是不同种类硬币面值的组合的和
	{
		bRet = TRUE;
		m_MinimumCoinsNum = M[m_nCoinsTypes][m_nMoney];
		out<<"最少硬币数："<<m_MinimumCoinsNum<<endl;
		out<<"最优解(Coin(面值,原数目,剩余数目))："<<endl;
		int size = m_pArrCoins.GetSize();
		for (int nIndex = 0; nIndex < size; nIndex++)
		{
			pCoin = (CCoin*)m_pArrCoins.GetAt(nIndex);
			if (pCoin->IsUsed())										//硬币被使用，则硬币是最优解的一部分
				out<<"Coin("<<pCoin->GetFaceValue()<<","<<pCoin->GetAvailableNum()<<","<<pCoin->GetRemainedNum()<<")"<<'	';
		}
	}
	else
	{
		out<<"此问题无解"<<endl;
	}

// 	for (int c = 0; c <= m_nCoinsTypes; c++)
// 	{
// 		for (int d = 0; d <= m_nMoney; d++)
// 			out<<M[c][d]<<'	';
// 		out<<endl;
// 	}	
// 
// 	for (int a = 0; a <= m_nCoinsTypes; a++)
// 	{
// 		for (int b = 0; b <= m_nMoney; b++)
// 			out<<K[a][b]<<'	';
// 		out<<endl;
// 	}
	return bRet;
}

BOOL CCoinsHandler::GreedyStrategy()
{
	BOOL bRet = FALSE;
	SortByFacevalue(FALSE);						//按面值降序排序

	int nMoney = m_nMoney;
	int nSize = m_pArrCoins.GetSize();
	CCoin* pCoin = new CCoin;
	int Vi;
	int UsedNum;
	int i;
	for (i = 0; i < nSize; i++)
	{
		if (nMoney <= 0)
			break;

		pCoin = (CCoin*)m_pArrCoins.GetAt(i);
		Vi = pCoin->GetFaceValue();
		if (nMoney < Vi)
			continue;

		UsedNum = nMoney / Vi;
		pCoin->UseCoins(UsedNum);
		nMoney -= UsedNum * Vi;
	}
	
	ofstream out("greedySolution.txt");
	if (nMoney == 0)										//有解
	{
		out<<"最优解(Coin(面值,原数目,剩余数目))："<<endl;
		for (int nIndex = 0; nIndex < nSize; nIndex++)
		{
			pCoin = (CCoin*)m_pArrCoins.GetAt(nIndex);
			if (pCoin->IsUsed())							//硬币被使用，则硬币是最优解的一部分
			{
				out<<"Coin("<<pCoin->GetFaceValue()<<","<<pCoin->GetAvailableNum()<<","<<pCoin->GetRemainedNum()<<")"<<'	';
				m_MinimumCoinsNum += pCoin->GetAvailableNum() - pCoin->GetRemainedNum();	//求各种面值硬币的使用数码
			}
		}
		out<<"\n最少硬币数："<<m_MinimumCoinsNum<<endl;
	}
	else
	{
		out<<"此问题无解"<<endl;
	}

	return bRet;
}