//?0-1背包問(wèn)題.cpp?:?定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
#include?“stdafx.h“
#include
#include?
using?namespace?std;
class?Knap
{
	friend?int?Knaspack（int?*?int?*?int?int）;
public:
	int?Bound（int?i）;
	void?Backtrack（int?i）;
	int?c;//背包承載物品的數(shù)量
	int?n;//物品數(shù)
	int?*w;//物品重量數(shù)組
	int?*p;//物品價(jià)值數(shù)組
	int?cw;//當(dāng)前重量
	int?cp;//當(dāng)前價(jià)值
	int?bestp;//當(dāng)前最有價(jià)值
};
void?Knap::Backtrack（int?i）
{
	if?（i>n）//到達(dá)葉子結(jié)點(diǎn)
	{
		bestp?=?cp;
		return;
	}
	if?（cw?+?w[i]?<=?c）//搜素左子樹(shù)
	{
		cw?+=?w[i];
		cp?+=?p[i];
		Backtrack（i?+?1）;
		cw?-=?w[i];
		cp?-=?p[i];
	}
	if?（Bound（i?+?1）>bestp）//搜索右子樹(shù)
		Backtrack（i?+?1）;
}
int?Knap::Bound（int?i）//計(jì)算上界
{
	int?cleft?=?c?-?cw;//剩余容量
	int?b?=?cp;
	//以物品單位重量?jī)r(jià)值遞減序裝入物品
	while?（i?<=?n&&w[i]?<=?cleft）
	{
		cleft?-=?w[i];
		b?+=?p[i];
		i++;
	}