knap.h

回朔解决0-1背包,里面有VC++的代码,可供大家参考,如里有误的,请和我联系

class Knap
{
	friend float Knapsack(float *,float *,float ,int);
private:
	float Bound(int i);
	void Backtrack(int i);
	float c;
	int n;
	float *w;
	float *p;
	float cw;
	float cp;
	float bestp;
};
float Knap::Bound(int i)
{
	float cleft=c-cw;
	float 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 (float)b;
}
void Knap::Backtrack(int i)
{
	if(i>n)
	{
		bestp=cp;
		return;
	}
	if(cw+w[i]<=c)
	{
		cw+=w[i];
		cp+=p[i];
		Backtrack(i+1);
		cw-=w[i];
		cp-=p[i];
	}
	if(Bound(i+1)>bestp)
		Backtrack(i+1);
}