0-1背包问题 回溯算法代码

// 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++;
	}