bag.cpp

这是用VC++编的算法分析中的实现!!有每个源程序

// Bag.cpp: implementation of the Bag class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "arithmeticdemo.h"
#include "Bag.h"

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

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

Bag::Bag()
{

}

Bag::~Bag()
{

}

Bag::Bound(int i)
{
	int cleft=c-cw;
	int b=cp;

	while(i<=n&&w[i]<=cleft)
	{
		cleft-=w[i];
		b+=p[i];
		i++;

	}

	if(i<=n)
		b+=p[i]/w[i]*cleft;

	return b;
}

void Bag::Backtrack(int i)

{
	if(i>n)
	{
		if(bestp<cp)
		{
			for(int j=1;j<=n;j++)
			bestx[j]=x[j];
			bestp=cp;

		}

		return;
	}

	if(cw+w[i]<=c)
	{             
		x[i]=1;
		cw+=w[i];
		cp+=p[i];
		Backtrack(i+1);
		cw-=w[i];
		cp-=p[i];

	}
	
	if(Bound(i+1)>bestp)
	{
		x[i]=0;
		Backtrack(i+1);

	}
}