0-1 背包问题 回溯法

#include
#include
using namespace std;

int goodsSum;
int capacityKnapsack;
int bestValue = INT_MIN;
vector* goodsWeight;
vector* goodsValue;
vector bestPut;

void backTrack(int depth, int weightKnapsack, int valueKnapsack, vector put);

int main()
{
	cout<<"请输入物品的数量：";
	cin>>goodsSum;
	cout<<"请输入背包的容量：";
	cin>>capacityKnapsack;
	cout<<"请依次输入 "<(goodsSum);
	goodsValue = new vector(goodsSum);
	cout<<(*goodsWeight).size();
	vector tempPut(goodsSum);

	for (int i = 0; i < goodsSum; i++)
	{
		cin>>(*goodsWeight)[i]>>(*goodsValue)[i];
	}

	backTrack(0, 0, 0, tempPut);

	cout< put)
{
	if (depth == goodsSum){
		if (valueKnapsack > bestValue){
			bestValue = valueKnapsack;
			bestPut.swap(put);
		}
	}
	else{
		put[depth] = false;
		backTrack(depth + 1, weightKnapsack, valueKnapsack, put);

		put[depth] = true;
		if (weightKnapsack + (*goodsWeight)[depth] <= capacityKnapsack){
			weightKnapsack += (*goodsWeight)[depth];
			valueKnapsack += (*goodsValue)[depth];
			backTrack(depth + 1, weightKnapsack, valueKnapsack, put);
		}
	}
}