knap.cpp

计算机算法设计与分析(王晓东)教材上相关源程序代码。 包括分治法(4)

#include"knap.h"
template<class Typew,class Typep>
void Knap<Typew,Typep>::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);
	}
	
}

template<class Typew,class Typep>
Typep Knap<Typew,Typep>::Bound(int i)
{

	//计算上界
	Typew cleft=c-cw;//剩余容量
	Typep b=cp;
	//以物品单位重量价值递减次序装入物品
	while(i<=n&& w[i]<=cleft)
	{
		cleft-=w[i];
		b+=p[i];
		i++;
	}

	//装满背包
	if(i<=n) b+=p[i]*cleft/w[i];
	return b;

}