分支限界法解0-1背包问题

一、   算法设计与分析：

（1）假设物品数为n，解空间：{(0,0,…,0),(0,0,…,1),…,(1,1,…,1)}，即为子集树，设计树节点结构如下：

struct Node {
      intvalue;           //搜索到该节点时的价值
      intweight;          //搜索到该节点时的总重量
      floatbound;        //搜索以该节点为根的子树能达到的价值上界
      intlevel;           //该节点所处层次，从0开始
      struct  Node *parent;//指向父节点
};
           

（2）采用优先队列的分支限界法，每次选择优先级最高的活结点进行扩展，优先级最高节点即能达到最大上界的节点，在此采用C++ STL提供的priority_queue，其内部为小根堆，重写cmp将其改为大根堆，cmp如下所示：

struct cmp {
      booloperator () (Node *a, Node *b) {
             returna->bound < b->bound;
      }
};
           

二、算法实现

struct Node {
	Node() {
		value = 0;
		weight = 0;
		level = 0;
		parent = 0;
		bound = 0;
	}
	int value;           //搜索到该节点时的价值
	int weight;          //搜索到该节点时的总重量
	float bound;		 //搜索以该节点为根的子树能达到的价值上界
	int level;           //该节点所处层次，从0开始
	struct  Node *parent;//指向父节点
};

struct cmp {
	bool operator () (Node *a, Node *b) {
		return a->bound < b->bound;
	}
};

struct Item{
	int ItemID;			//物品编号
	int value;			//物品价值
	int weight;			//物品重量
	float ratio;		//价值/重量
};

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

#include <iostream>
#include <queue>
#include "Structure.h"
#include <algorithm>
#define N 10               //物品数为N
using namespace std;
int branchAndBound(Item items[], int c);
float maxBound(Node *node, Item items[], int c);

int maxSize=0;
int searchCount=0;
int main() {
	//int v[N] = {40,25, 25 };//物品价值
	//int w[N] = {20,15, 15 };//物品重量
	//int w[N] = {2,7,3,4,8,5,8,6,4,16};
	//int v[N] = {15,25,8,9,15,9,13,9,6,14};
	int w[N] = {2,8,4,4,8,7,8,5,16,16};
	int v[N] = {15,25,9,9,15,12,12,6,14,9 };
	int c = 34;			    //背包容量
	Item items[N];
	int maxVlue;

	for (int i = 0; i < N; i++) {
		items[i].ItemID = i;
		items[i].value = v[i];
		items[i].weight = w[i];
		items[i].ratio = (float)v[i] / w[i];
	}
	sort(items,items+N,ItemCmp);//按价值率排序
	
	cout << "商品价值依次为："<<endl;
	for (int i = 0; i < N; i++) {
		cout << v[i] << " ";
	}
	cout << endl;
	cout << "商品重量依次为：" << endl;
	for (int i = 0; i < N; i++) {
		cout << w[i] << " ";
	}
	cout << endl;
	cout << "选取方案为:(1为取)" << endl;
	maxVlue = branchAndBound(items, c);
	cout << "最大价值为:" << maxVlue << endl;
	cout << "队列中元素最多为：" << maxSize << endl;
	cout << "搜索次数为：" << searchCount << "" << endl;
	return 0;
}

int branchAndBound(Item items[], int c) {
	int x[N] = { 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;
}
           

三、算法结果分析

采用数据集：w[N] = {5,4,8,12,13}，v[N] = {7，9，15，21，24}，c=20

计算结果如下：

最大价值为36个，队列中元素最多为5个，搜索次数为19次，而采用FIFO队列的算法，队列中元素最多为32个，搜索次数为63次。可见采用优先队列的分支限界法大大降低了空间复杂度和时间复杂度度（搜索次数）。