//?0-1背包問題.cpp?:?定義控制臺應用程序的入口點。
//
#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;//背包承載物品的數量
	int?n;//物品數
	int?*w;//物品重量數組
	int?*p;//物品價值數組
	int?cw;//當前重量
	int?cp;//當前價值
	int?bestp;//當前最有價值
};
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）;
}
int?Knap::Bound（int?i）//計算上界
{
	int?cleft?=?c?-?cw;//剩余容量
	int?b?=?cp;
	//以物品單位重量價值遞減序裝入物品
	while?（i?<=?n&&w[i]?<=?cleft）
	{
		cleft?-=?w[i];
		b?+=?p[i];
		i++;
	}