编辑代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n;
int c;
struct Item
{
	int ItemID;
	int value;
	int weight;
	int ratio;
};
struct Node
{
	Node(){
		value = 0;
		weight = 0;
		level = 0;
		parent = 0;
		bound = 0;
	}
	int value;
	int weight;
	int bound;
	int level;
	struct Node *parent;
};
struct cmp
{
	bool operator()(Node *a, Node *b){
		return a->bound < b->bound;
	}
};
bool Itemcmp(Item item1, Item item2);
int branchAndBound(Item items[], int c);
int searchCount = 0;
int maxSize = 0;
float maxBound(Node *node, Item items[], int c);

int main(){
	int maxValue;
	cout << "请输入物品的个数:";
	cin >> n;
	cout << "请输入背包容量:";
	cin >> c;
	int *w = new int[n];
	int *v = new int[n];
	cout << "请输入" << n << "个物品的质量:" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> w[i];
	}
	cout << "请输入" << n << "个物品的价值:" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	Item *items = new Item[n];
	for (int i = 0; i < n; i++)
	{
		items[i].ItemID = i;
		items[i].value = v[i];
		items[i].weight = w[i];
		items[i].ratio = 1.0*v[i] / w[i];
	}

	sort(items, items + n, Itemcmp);
	cout << "商品的价值依次为:";
	for (int i = 0; i < n; i++)
	{
		cout << v[i] << "  ";
	}
	cout << endl;
	cout << "商品的质量分别为:";
	for (int i = 0; i < n; i++)
	{
		cout << w[i] << " ";
	}
	cout << endl;
	cout << "选取方案为:" << endl;
	maxValue = branchAndBound(items, c);
	cout << "最大价值为:" << maxValue;
	getchar();
	getchar();
	getchar();
	delete []w;
	delete []v;
}

bool Itemcmp(Item item1, Item item2){
	return item1.ratio > item2.ratio;
}

int branchAndBound(Item items[], int c){
	int *x = new int[n];
	for (int i = 0; i < n; i++)
	{
		x[i] = 0;
	}
	int maxValue;
	Node *maxNode = new Node();
	priority_queue<Node *, vector<Node *>, cmp> maxQueue;
	Node *firstNode, *curNode;
	
	searchCount = 1;
	firstNode = new Node();
	firstNode->bound = maxBound(firstNode, items, c);
	firstNode->parent = NULL;
	maxQueue.push(firstNode);
	maxValue = 0;
	maxNode = firstNode;
	while (!maxQueue.empty()){
		curNode = maxQueue.top();
		maxQueue.pop();
		if (curNode->weight + items[curNode->level].weight <= c){
			Node *leftNode = new Node();
			leftNode->value = curNode->value + items[curNode->level].value;
			leftNode->weight = curNode->weight + items[curNode->level].weight;
			leftNode->level = curNode->level + 1;
			leftNode->parent = curNode;
			leftNode->bound = curNode->bound;
			if (leftNode->level<n)
			{
				maxQueue.push(leftNode);
				searchCount++;
			}
			if (maxValue<leftNode->value)
			{
				maxValue = leftNode->value;
				maxNode = leftNode;
			}
		}

		if (maxBound(curNode, items, c)>maxValue){
			Node *rightNode = new Node();
			rightNode->value = curNode->value;
			rightNode->weight = curNode->weight;
			rightNode->level = curNode->level + 1;
			rightNode->parent = curNode;
			rightNode->bound = maxBound(rightNode, items, c);
			if (rightNode->level<n)
			{
				maxQueue.push(rightNode);
				searchCount++;
			}
		}
		if (maxQueue.size()>maxSize)
		{
			maxSize = maxQueue.size();
		}
	}
	curNode = maxNode;
	while (curNode)
	{
		int tempValue = curNode->value;
		curNode = curNode->parent;
		if (curNode&&curNode->value != tempValue){
			x[items[curNode->level].ItemID] = 1;
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << x[i] << "  ";
	}
	cout << endl;
	return maxValue;
}

float maxBound(Node *node, Item items[], int c){
	float maxValue;
	int restCapacity;
	int i;

	maxValue = node->value;
	restCapacity = c - node->weight;
	i = node->level;

	while (i<n&&restCapacity>items[i].weight)
	{
		maxValue += items[i].value;
		restCapacity -= items[i].weight;
		i++;
	}
	if (restCapacity!=0)
	{
		maxValue += restCapacity*items[i].ratio;
	}
	return maxValue;
}