概念：

  分支限界采用的是广搜。

  优先队列采用的是队列里最优的出队。（这里采用最大堆来实现活结点优先队列，最大堆以活结点的界值作为优先级）

说明：

    对于优先队列式分支限界法解01背包，实际上是广搜遍历生成树的过程。因为01背包。背包只有选和不选。所以该生成树是一个二叉树。假设规定左叉标1（代表选择该物品装入背包），右叉标0（代表不选择该物品装入背包）。给定示例输入：

背包容量c=10

物品个数n=5

物品重量w={2，2，6，5，4}

物品价格p={6，3，5，4，6}

步骤：

    左子树的解的上界与父节点相同，不用计算。右子树的解的界值：较好的就算方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直到装不下时，再装入该物品的一部分来装满背包。由此得到的价值是右子树中解的上界（尽管这不是一个可行解，但可以证明其价值是最优值的上界）。

1.排好序的情况：

物品重量w={2，2，4，6，5}

物品价格p={6，3，6，5，4}

2.一层一层的将活结点加入到活结点优先队列中：



说明：

    0.程序先是将1，2结点加入到队列中，由于1的界大于2的 界，所以选择1结点继续扩展（继续向下搜索）---进入到3，4结点的选择。由于父节点2没有出队。所以相继的5，6结点就被沉默掉了，故第二层只考虑3，4结点，3选择了2号物品后没有超重，4的界也大于当前背包的价格6+3=9.所以3，4都被加入到活结点，又由于3的界大于4的界，所以选择3作为扩展结点，继续向下进行扩展。。。。。。直到叶子结点。。。。程序结束

    1.该生成树中：只要左儿子结点没超重就把他加入到活结点优先队列中来。只要右儿子结点的界值大于当前背包的价值，就将右儿子结点也加入到活结点优先队列中来。当进入到下一层的搜索时，会从上一层的活结点队列中选择最优的那个结点（界值最大的）作为父节点（扩展结点）进行扩展，向下搜索。而上一层没有机会出队的活结点将暂时被沉默掉，等待出队的机会

   2.下面再附上MaxKanpsack（）函数的运行数据变化图。方便更快速的理解代码。

      注解：下图中：i=4，  a'''=add(14>10),add其实是addlivenode（）函数，这里的14表示当前结点下（选择1，2，3，4号物品后背包重量为14=2+2+4+6，明显大于了背包的重量10，所以a'''=add（）也应该划叉，即该结点被终结了，因为超重了。下文的i=5，a'''=add(13>10)分析同上。）

     各个节点界的计算：1结点：（6+3+6）+（10-2-2-4）*（5/6）=16.6666            

                                     2结点：（3+6）+（10-2-4）*（5/6）=12.3333         ...........................

                                     8结点：  （6+3）+（10-2-2）*（5/6）=14.00000

                                     16结点： （6+3+6）+（10-2-2-4）*（4/5）=16.60000

                                     34结点： （6+3+6）+（10-2-2-4）* 0=15

                                     左儿子结点的界不用算，直接继承父节点的界（左儿子的界=父节点的界）3结点的界=1结点的界=7结点的界=16.66

                    

过程说明：i=1时：第一层广搜：1和2结点作比较。由于1和2的界（16.6，12.3）都大于当前背包的价值6，故都加入活结点的优先队列中。又1的 界大于2的界，选择1作扩展结点（父节点）进入下一层。............

                i=3时，背包价格：15=6+3+6；而8号的界为14<15(8号界小于当前背包重量，不加入活结点优先队列中)，15号结点对应的背包重量是2+2+4+6=14>10(背包重量)，超重了。



代码如下：

#include<stdio.h>
#include <iostream>
using namespace std;
typedef int Typew;
//typedef int Typep;
//物品类
class Object{
	friend float Knapsack(Typew *, float *, Typew, int, int *);
    public:
	int operator <= (Object a) const{
      return (d >= a.d);
}

private:
	int ID; //物品编号
	float d; //单位重量价值
};
//树结点类
class bbnode{
	friend class Knap;
	friend float Knapsack(Typew *, float *, Typew, int, int *);
private:
	bbnode *parent; //指向父节点的指针
	int LChild; //如果是左儿子结点取1，也即说明该物品已装进背包
};
//堆结点类
class HeapNode{
	friend class Knap;
	friend class MaxHeap;
public:
	operator float()const{return uprofit;};
private:
	float uprofit, //结点的价值上界
		  profit; //结点所相应的价值
	Typew weight; //结点所相应的重量
	int level; //活结点在子集树中所处的层序号
	bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针
};
//最大堆类
class MaxHeap{
public:
	MaxHeap(int maxElem)
	{
		HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留
		capacity = maxElem;
		size = 0;
	}
	void InsertMax(HeapNode *newNode);
	HeapNode DeleteMax(HeapNode* &N);
private:
	int capacity;
    int size;
    HeapNode **HeapElem;
};
//0-1背包问题的主类
class Knap{
	//Knapsack主函数功能：解决初始化、求解最优值和最优解、回收内存
	friend float Knapsack(Typew *, float *, Typew, int, int *);
public:
	float MaxKnapsack();
private:
	MaxHeap *H;
	//Bound辅助Maxknapsack函数：计算结点价值上界
	float Bound(int i);
	//AddLiveNode辅助Maxknapsack函数：将活结点插入子集树和优先队列中
	void AddLiveNode(float up, float cp, Typew cw, int ch, int level);
	bbnode *E; //指向扩展结点的指针
	Typew c; //背包容量
	int n; //物品总数
	Typew *w; //物品重量数组（以单位重量价值降序）
	float *p; //物品价值数组（以单位重量价值降序）
	Typew cw; //当前装包重量
	float cp; //当前装包价值
	int *bestx; //最优解
};
//这是博客上大牛自己写的，原教材上没有
void MaxHeap::InsertMax(HeapNode *newNode)
{
	//极端情况下暂未考虑,比如堆容量已满等等
	int i = 1;
		for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit; i /= 2)
		{
			HeapElem[i] = HeapElem[i/2];
		}
		HeapElem[i] = newNode;
}
//这是博客上大牛自己写的，原教材上没有
HeapNode MaxHeap::DeleteMax(HeapNode *&N)

{
	//极端情况下暂未考虑
		if(size >0 )
		{
			N = HeapElem[1];
			//从堆顶开始调整
			int i = 1;
			while(i < size)
			{
	if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit > HeapElem[i*2 +1]->uprofit)
				{
		HeapElem[i] = HeapElem[i*2];
            	i = i*2;
				}
            	else
				{
					if(i*2 <= size)
					{
                        	HeapElem[i] = HeapElem[i*2];
							i = i*2;
					}
					else
						break;
				}
			}
			if(i < size)
				HeapElem[i] = HeapElem[size];
		}
		size--;
		return *N;
}
float Knap::MaxKnapsack()
{
	H = new MaxHeap(1000);
	bestx = new int [n+1];
	//初始化,为处理子集树中的第一层做准备,物品i处于子集树中的第i层
	int i = 1; //生成子集树中的第一层的结点
	E = 0; //将首个扩展点设置为null，也就是物品1的父节点
	cw = 0;
	cp = 0;
	float bestp = 0; //当前最优值
    float up = Bound(1); // 选取物品1之后的价值上界
	//当选择左儿子结点时，上界约束up不用关心，重量约束wt需要考虑。因为上界约束跟父节点相同。
	//当选择右儿子结点时，上界约束up需要考虑，重量约束不需要考虑。因为父节点和该结点重量相同。
	while (i != n+1)
	{
		//检查当前扩展结点的左儿子结点
		int wi=w[i];
		int pi=p[i];
		int cp1=cp;
		int cw1=cw;
		int test=cw1+cp1;
		Typew wt = cw + w[i]; //当前选择物品i之后的总重量wt
		if(wt <= c) //背包能将物品i装下，也即当前扩展结点的左儿子结点可行
		{
			if(cp + p[i] > bestp)
				bestp = cp +pi;
				//bestp = cp + p[i]
			AddLiveNode(up, cp + p[i], cw + w[i], 1, i);
		}
        //检查当前扩展结点的右儿子结点
		up = Bound(i + 1); //未选择物品i之后的价值上界
		if(up >= bestp)
			AddLiveNode(up, cp, cw, 0, i);
		//从优先队列中选择价值上界最大的结点成为扩展结点
		HeapNode* N;
		H->DeleteMax(N);
		E = N->elemPtr;
		cw = N->weight;
		cp = N->profit;
		up = N->uprofit;
		i = N->level + 1; //准备生成N.level+1层的子集树结点
	}
	//从子集树中的某叶子结点开始构造当前最优解
    for (int i = n; i > 0; i--)
	{
	bestx[i] = E->LChild;
	E = E->parent;
	}
	return cp;
}

float Knap::Bound(int i)
{
	Typew cleft = c - cw;
	float b = cp;
	while (i<=n && w[i] <= cleft)
	{
	cleft -= w[i];
	b += p[i];
	i++;
	}
	if(i<=n) b += p[i]/w[i] * cleft;
    return b;
}
void Knap::AddLiveNode(float up, float cp, Typew cw, int ch, int level)
{
	bbnode *b=new bbnode;
    b->parent=E;
    b->LChild=ch;
	HeapNode *N = new HeapNode;
    N->uprofit=up;
    N->profit=cp;
    N->weight=cw;
    N->level=level;
	N->elemPtr=b;
	H->InsertMax(N);
  }
   //Knapsack返回最大价值，最优值保存在bestx
   float Knapsack(Typew *w, float *p, Typew c, int n, int *bestx)
   {//数组w、p和bestx中下标为0的元素保留不用
	//初始化
	Typew W = 0;
	float P = 0;
	Object *Q = new Object[n];
	for(int i =1; i<=n; i++)
	{
	Q[i-1].ID = i;
	Q[i-1].d = 1.0*p[i]/w[i];
	P += p[i];
		W += w[i];
	}
	//所有物品的总重量小于等于背包容量c
	if (W <= c)
	{
		for(int i =1; i<=n; i++)
	{
				bestx[i] = p[i];
		}
	return P;
	}
	//所有物品的总重量大于背包容量c,存在最佳装包方案
    //sort(Q,n);对物品以单位重量价值降序排序
	//1.对物品以单位重量价值降序排序
	//采用简单冒泡排序
	for(int i = 1; i<n; i++)
		for(int j = 1; j<= n-i; j++)
		{
			if(Q[j-1].d < Q[j].d)
			{
				Object temp = Q[j-1];
				Q[j-1] = Q[j];
				Q[j] = temp;
			}
		}
    //Knapsack主函数功能：解决初始化、求解最优值和最优解、回收内存
	Knap K;
	K.p = new float [n+1];
	K.w = new Typew [n+1];
	for(int i = 1; i<=n; i++)
	{
		K.p[i] = p[Q[i-1].ID];//（以单位重量价值降序排序）
		K.w[i] = w[Q[i-1].ID];//（以单位重量价值降序排序）
	}
	K.cp = 0;
	K.cw = 0;
	K.c = c;
	K.n = n;
	//2.MaxKnapsack（）负责分支限界的搜索，并找出最优值------这是一个填二叉树的过程
	float bestp = K.MaxKnapsack();
	for(int i = 1; i<=n; i++)
	{
		bestx[Q[i-1].ID] = K.bestx[i];
	}
	delete [] Q;
	delete [] K.w;
	delete [] K.p;
	delete [] K.bestx;
	delete [] K.H;
	return bestp;
}
int main(int argc, char* argv[])
{
	const int N = 5;
        Typew c=10; //背包容量
	int bestx[N+1]; //最优解
	int bestp; //最优值
	//需要说明的是，这里的数组p[]和w[]的第一个元素是-1，这是因为我在操作过程中
	//都是从数组元素的1开始的，而我们知道数组中第一个元素是0号元素，所以我这里用-1填上
	Typew w[]={0,2,2,6,5,4};//物品重量
	float p[]={0,6,3,5,4,6};//物品价值
//排好序之后的：
//p【6，3，6，5，4】
//w【2，2，4，6，5】
	bestp = Knapsack(w, p, c, N, bestx);
	cout<<"物品总数N = "<< N<<",背包容量C = "<< c<<endl;
	for (int i = 1; i <= N; i++)
	{
		if(i ==1 ) cout<<"重量数组：";
		cout<<w[i];
		if(i != N) cout<<",";
		else
			cout<<endl;
	}
	for (int i = 1; i <= N; i++)
	{
		if(i ==1 ) cout<<"价值数组：";
		cout<<p[i];
		if(i != N) cout<<",";
		else
			cout<<endl;
	}
	for (int i = 1; i <= N; i++)
	{
		if(i ==1 ) cout<<"是否选取：";
		cout<<bestx[i];
		if(i != N) cout<<",";
		else
			cout<<endl;

	}
	cout<<"背包最优价值："<<bestp<<endl;
	system("pause");
	return 0;
}

 


上述代码对于w={3,4,5}    p={4,5,6}  c=6  执行的结果有误

再附上修正后的：

#ifndef BEIBAO_H
#define  BEIBAO_H
#include <math.h>
#include <iostream>
using namespace std;
//子空间中节点类型
class BBnode{
public:
	BBnode*  parent;   //父节点
	bool leftChild;   //左儿子节点标志
	BBnode(BBnode* par,bool ch){
		parent=par;
		leftChild=ch;
	}
	BBnode(){

	}
};

class HeapNode {
public:
	BBnode* liveNode; // 活结点
	double  upperProfit; //结点的价值上界
	double  profit; //结点所相应的价值
	double  weight; //结点所相应的重量
	int     level; // 活结点在子集树中所处的层次号

	//构造方法
	 HeapNode(BBnode* node, double up, double pp , double ww,int lev){
		liveNode = node;
		upperProfit = up;
		profit    = pp;
		weight    = ww;
		level    = lev;
	}
	 HeapNode(){

	 }
	 int compareTo(HeapNode o) {
		double xup =o.upperProfit;
		if(upperProfit < xup)
			return -1;
		if(upperProfit == xup)
			return 0;
		else
			return 1;
	}
};

class Element  {
public:
	int id;
	double d;
	Element(){

	}
	Element(int idd,double dd){
		id=idd;
		d=dd;
	}
	int compareTo(Element x){
		double xd=x.d;
		if(d<xd)return -1;
		if(d==xd)return 0;
		return 1;
	}
	 bool equals(Element x){
		return d==x.d;
	}
};

class MaxHeap{
public:
	 HeapNode *nodes;
	 int nextPlace;
	 int maxNumber;
	 MaxHeap(int n){
		maxNumber = pow((double)2,(double)n);
		nextPlace = 1;//下一个存放位置
		nodes = new HeapNode[maxNumber];
	}
	 MaxHeap(){
	 }
    void put(HeapNode node){
		nodes[nextPlace] = node;
		nextPlace++;
		heapSort(nodes);
	}
	HeapNode removeMax(){
		HeapNode tempNode = nodes[1];
		nextPlace--;
		nodes[1] = nodes[nextPlace];
		heapSort(nodes);
		return tempNode;
	}
	 void heapAdjust(HeapNode *  nodes,int s,int m){
		HeapNode rc = nodes[s];
		for(int j=2*s;j<=m;j*=2){
			if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)
				++j;
			if(!(rc.upperProfit<nodes[j].upperProfit))
				break;
			nodes[s] = nodes[j];
			s = j;
		}
		nodes[s] = rc;
	}
    void heapSort(HeapNode * nodes){
		for(int i=(nextPlace-1)/2;i>0;--i){
			heapAdjust(nodes,i,nextPlace-1);
		}
	}
} ;

#endif

//子空间中节点类型

double c=10;
const int n=5;
double *w;
double *p;
double cw;
double cp;
int    *bestX;
MaxHeap * heap;


//上界函数bound计算结点所相应价值的上界
 double bound(int i){
	double cleft=c-cw;
	double b=cp;
	while(i<=n&&w[i]<=cleft){
		cleft=cleft-w[i];
		b=b+p[i];
		i++;
	}
	//装填剩余容量装满背包
	if(i<=n)
		b=b+p[i]/w[i]*cleft;
	return b;
}
//addLiveNode将一个新的活结点插入到子集树和优先队列中
 void addLiveNode(double up,double pp,double ww,int lev,BBnode* par,bool ch){
	//将一个新的活结点插入到子集树和最大堆中
	BBnode *b=new BBnode(par,ch);
	HeapNode  node =HeapNode(b,up,pp,ww,lev);
	heap->put(node);
}
 double MaxKnapsack(){
	//优先队列式分支限界法，返回最大价值，bestx返回最优解
	BBnode * enode=new BBnode();
	int i=1;
	double bestp=0;//当前最优值
	double up=bound(1);//当前上界
	while(i!=n+1){//非叶子结点
		//检查当前扩展结点的左儿子子结点
		double wt=cw+w[i];
		if(wt<=c){
			if(cp+p[i]>bestp)
				bestp=cp+p[i];
			addLiveNode(up,cp+p[i],cw+w[i],i+1,enode,true);
		}
		up=bound(i+1);
		if(up>=bestp)
			addLiveNode(up,cp,cw,i+1,enode,false);
		HeapNode node =heap->removeMax();
		enode=node.liveNode;
		cw=node.weight;
		cp=node.profit;
		up=node.upperProfit;
		i=node.level;
	}
	for(int j=n;j>0;j--){

		bestX[j]=(enode->leftChild)?1:0;
		enode=enode->parent;
	}
	return cp;
}


 double knapsack(double *pp,double *ww,double cc,int *xx){
	//返回最大值，bestX返回最优解
	c=cc;
	//n=sizeof(pp)/sizeof(double);
	//定义以单位重量价值排序的物品数组
	Element *q=new Element[n];
	double ws=0.0;
	double ps=0.0;
	for(int i=0;i<n;i++){
		q[i]=Element(i+1,pp[i+1]/ww[i+1]);
		ps=ps+pp[i+1];
		ws=ws+ww[i+1];
	}
	if(ws<=c){
		return  ps;
	}
	p=new double[n+1];
	w=new double[n+1];
	for(int i=0;i<n;i++){
		p[i+1]=pp[q[i].id];
		w[i+1]=ww[q[i].id];
	}
	cw=0.0;
	cp=0.0;
	bestX = new int[n+1];
	heap = new MaxHeap(n);
	double bestp = MaxKnapsack();
	for(int j=0;j<n;j++)
		xx[q[j].id]=bestX[j+1];

	return  bestp;

}

int main(){

	//w=new double[4];
	double w[6]={0,2,2,6,5,4};
	 double p[6]={0,6,3,5,4,6};
	int *x = new int[4];
	double m = knapsack(p,w,c,x);


	cout<<"*****分支限界法*****"<<endl;
	cout<<"*****物品个数：n="<<n<<endl;
	cout<<"*****背包容量：c="<<c<<endl;
	cout<<"*****物品重量数组：w= {"<<w[3]<<" "<<w[1]<<" "<<w[2]<<"}"<<endl;
	cout<<"*****物品价值数组：v= {"<<p[3]<<" "<<p[1]<<" "<<p[2]<<"}"<<endl;
	cout<<"*****最优值：="<<m<<endl;
	cout<<"*****选中的物品是:";
	for(int i=1;i<=3;i++)
		cout<<x[i]<<" ";
	cout<<endl;
	return 0;
}


图片：

问题描述:
 某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。

          

 结果为: 1 3 2 4 1

 

 

问题分析

解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表。
活结点m在优先队列中的优先级定义为：活结点m对应的子树费用下界lcost。
lcost=cc+rcost，其中，cc为当前结点费用，rcost为当前顶点最小出边费用加上剩余所有顶点的最小出边费用和。
优先队列中优先级最大的活结点成为下一个扩展结点。
排列树中叶结点所相应的载重量与其优先级（下界值）相同，即：叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值。
与子集树的讨论相似，实现对排列树搜索的优先队列式分支限界法也可以有两种不同的实现方式：(旅行售货员问题采用第一种实现方式。)


用优先队列来存储活结点。优先队列中每个活结点都存储从根到该活结点的相应路径。
用优先队列来存储活结点，并同时存储当前已构造出的部分排列树。优先队列中的活结点不必存储从根到该活结点的相应路径，该路径必要时从存储的部分排列树中获得。



令Minout[i]代表顶点i的最小出边费用。图中：
   Minout[1]=4                 Minout[2]=5

   Minout[3]=5                 Minout[4]=4


如，在扩展顶点D处：
 rcost=Minout[3]+Minout[2]+Minout[4]=14

  其中:Minout[3]:当前顶点最小出边

     Minout[2],Minout[4]:剩余所有顶点最小出边




算法描述

要找最小费用旅行售货员回路，选用最小堆表示活结点优先队列。
算法开始时创建一个最小堆，用于表示活结点优先队列。
堆中每个结点的优先级是子树费用的下界lcost值。
计算每个顶点i的最小出边费用并用minout[i]记录
如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法结束。





 基于优先队列式分支限界的旅行售货员问题求解算法，采用限界函数lcost ，作为优先级，不断调整搜索方向，选择最有可能取得最优解的子树优先搜索；同时，根据限界函数lcost进行剪枝，剪掉不包含最优解的分支。

算法的while循环完成对排列树内部结点的扩展。对于当前扩展结点，算法分两种情况进行处理。


令s表示结点在排列树中的层次（节点B为第0层）。考虑排列树层次s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。

 (1).检测图G是否存在一条从顶点x[n-2]到顶点x[n-1]的边和一条从顶点x[n-1]到顶点1的边。

 (2). 如果这两条边都存在，则找到一条旅行员售货回路。

 (3).此时，算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bestc。

 (4). 如果是，则必须更新当前最优值bestc和当前最优解bestx。

if(cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1] < bestc )
{    // 找到更优的旅行路径
	 for (int j = 0; j <= n-1; j++) bestx[j] = x[j];
	 bestc = cc + a[x[n-2]][x[n-1]] + a[x[n-1]][1];    
}



令x记录当前解，s表示结点在排列树中的层次（结点B为第0层）。当扩展结点所处的层次s<n-2时，算法依次产生当前扩展结点的所有儿子结点。

 (1). 由于当前扩展结点所相应的路径是x[0: s]，该扩展结点可行儿子结点是从剩余顶点x[s+1: n-1]中选取的顶点x[i]，且(x[s]，x[i])是所给有向图G中的一条边。

 (2).对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x[0:s]，x[i])的费用cc和相应的下界lcost。

 (3).当lcost<bestc时，将这个可行儿子结点插入到活结点优先队列中,否则,将剪去以该儿子结点为根的子树。




while循环的终止条件：排列树的一个叶结点成为当前扩展结点, 算法结束。
当s=n-1时，已找到的回路是x[0: n-1]，它已包含图G的所有n个顶点。
因此，当s=n-1时，相应的扩展结点表示一个叶结点。该叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值。因为一旦一个叶结点成为当前扩展结点，剩余活结点的下界值(lcost值)，都大于等于当前叶子节点处已找到的回路的费用。它们都不可能导致费用更小的回路。
因此，已找到叶结点所相应的回路，是一个最小费用旅行售货员回路，算法结束。
算法结束时，返回找到的最小费用，相应的最优解由数组v给出




优先队列式分支限界法求解TSP问题
 s代表当前节点在排列树中层次，从排列树的根节点到当前结点的路径为x[0:s]，进一步搜索的顶点为x[s+1: n-1]
class MinHeapNode {
Friend Traveling <Type>;
Public:
  	Operator Type () const { return lcost;}
private:
	Type lcost,  费用下界
	Type cc, 当前费用
	Type rcost, 顶点最小出边费用和(顶点为：x[s:n-1])
	int s,  当前结点在排列树中的层次;
	Int *x,  存储解（结点路径）
}

下界：lcost=cc+rcost

Minout[i]：顶点i的最小费用出边

初始化时：cc=0, s=0, x[0]=1, x[1: n-1]=(2,3,…, n)



初始化时:bestc为较大数值




样例




分析演示

代码
#include <iostream>
#define NO_PATH -1         //没有通路
#define MAX_WEIGHT 4000

using namespace std;

int N;                     //城市数目
int City_Graph[100][100];  //保存图信息
int x[100];                //x[i]保存第i步遍历的城市
int isIn[100];             //保存 城市i是否已经加入路径
int bestw;                 //最优路径总权值
int cw;                    //当前路径总权值
int bestx[100];            //最优路径
//-----------------------------------------------------------------
void Travel_Backtrack(int t){        //递归法
    int i,j;
    if(t>N){                         //走完了，输出结果
        for(i=1;i<=N;i++)            //输出当前的路径
            cout<<x[i];
        cout<<endl;
        if(cw < bestw){              //判断当前路径是否是更优解
            for (i=1;i<=N;i++){
                bestx[i] = x[i];
            }
            bestw = cw+City_Graph[x[N]][1];
        }
        return;
    }
    else{
        for(j=1;j<=N;j++){           //找到第t步能走的城市
            if(City_Graph[x[t-1]][j] != NO_PATH && !isIn[j]){ //能到而且没有加入到路径中
                isIn[j] = 1;
                x[t] = j;
                cw += City_Graph[x[t-1]][j];
                Travel_Backtrack(t+1);
                isIn[j] = 0;
                x[t] = 0;
                cw -= City_Graph[x[t-1]][j];
            }
        }
    }
}
int main(){
    int i;
    cout<<"请输入城市数目:";
    cin>>N;
    for(int i=1;i<=N;i++){
        cout<<"请输入第"<<i<<"座城市的路程信息(不通请输入-1):";
        for(int j=1;j<=N;j++){
            cin>>City_Graph[i][j];
        }
    }

    //测试递归法
    for (i=1;i<=N;i++){
        x[i] = 0;               //表示第i步还没有解
        bestx[i] = 0;           //还没有最优解
        isIn[i] = 0;            //表示第i个城市还没有加入到路径中
    }

    x[1] = 1;                   //第一步 走城市1
    isIn[1] = 1;                //第一个城市 加入路径
    bestw = MAX_WEIGHT;
    cw = 0;
    Travel_Backtrack(2);        //从第二步开始选择城市
    cout<<"最优值为:"<<bestw;
    cout<<"最优解为:";
    for(i=1;i<=N;i++){
        cout<<bestx[i];
    }
   cout<<endl;
}




测试样例
数据与例子中的数据相同。
输入:

4

-1 30 6 4

30 -1 5 10

6 5 -1 20

4 10 20 -1
输出

1234

1243

1324

1342

1423

1432

最优值为:25最优解为:1423

继续学习装载问题

上一篇我们学习了用队列式分支限界法求解，这一次采用优先队列式分支限界法来求解。

有一批共n个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。

可证明，采用如下策略可以得到一个最优装载方案：先尽可能的将第一艘船装满，其次将剩余的集装箱装到第二艘船上。

其实质是要求第一艘船的最优装载。 其解空间树是一棵子集树。

《算法设计与分析》-王晓东著 一书P164-165给出的代码同样是存在问题，无法运行的。主要表现是MaxHeap的定义没有给出，循环变量i的初值是1，计算扩展结点相应载重量的for循环以及构造当前最优解的for循环中终止条件都没有考虑j=0的情况；

对代码的修订如下：

package ch06.book;


import java.util.PriorityQueue;

public class PiorityBBLoading {

	static PriorityQueue<HeapNode> heap = null;
	static int bestWeight = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] weight = {10,40,40};
		int capacity = 50;
		int [] bestSolution = new int[weight.length];

		bestWeight = maxLoading(weight, capacity, bestSolution);
		System.out.printf("the best load weight is: %d \r\n", bestWeight);
		System.out.print("the node path of best solution:");
		for(int i=0; i<bestSolution.length; i++) {
			System.out.printf("\t%d", bestSolution[i]);
		}
	}

	public static int maxLoading(int []containerWeight , int capacity, int[] bestSolution) {
		
		// initialization 
		heap = new PriorityQueue<HeapNode>();
		int n = containerWeight.length -1; // n+1 represents the number of boxes, equals with the number of tree levels;
		BBNode expandNode = null;
				
		int i = 0;     // represent the node level of current expand node;
		int expandWeight = 0;   // the weight of load at the expand node;
		
		// declare the remain weight array
		int [] remains = new int[n +1];
		remains[n] = 0;
		// backward calculate the remain weight for each node;
		for (int j = n-1; j>=0; j--) {
			remains[j] = remains[j+1] + containerWeight[j+1];
		}
		
		// search the binary solution space tree until reach a leaf node;
		// reach a leaf node when i = n+1;
		while (i != n +1) {
			// check left child node;
			System.out.printf("checking left child, trying weight:%d + %d \r\n", expandWeight , containerWeight[i]);
			if (expandWeight + containerWeight[i] <= capacity) {
				// the overall weight include left child node is less than capacity, so left child is a feasible node;
				// then put the left child node in queue;
				
				int nodePriority = expandWeight + containerWeight[i]+ remains[i];
				System.out.printf("try put left child in Heap: level %d, priorty: %d \r\n", i, nodePriority);
				addLiveNode(nodePriority, i+1, expandNode, true);
			}
			// right child node is always feasible;
			System.out.printf("try put right child in Heap: level %d, priorty: %d \r\n", i, expandWeight + remains[i]);
			
			addLiveNode(expandWeight + remains[i], i+1, expandNode, false);
			
			// retrieve next expand node;	
			HeapNode node = heap.poll();
			i = node.level;
			expandNode = node.liveNode;
			expandWeight = node.upperLimitWeight - remains[i-1];
			System.out.printf("get next expand node in Heap and process: level:%d, node weight: %d\r\n", i, expandWeight);
		}
		// build the best solution 
		for(int j = n; j>=0; j--) {
			bestSolution[j] = expandNode.isLeftChild? 1:0;
			
			expandNode = expandNode.parent;
		}
		return expandWeight;
	}
	
	public static void addLiveNode(int upLimit, int level, BBNode parent, boolean isLeft) {
		// put this live node in to MaxHeap of live node;
		BBNode b = new BBNode(parent, isLeft);
		HeapNode node = new HeapNode(b, upLimit, level);
		heap.add(node);
	}

	/**
	 * This internal class represent a solution space tree node;
	 * @author wanyongquan
	 *
	 */
 static class BBNode{
	BBNode parent;
	boolean isLeftChild; 
	
	 BBNode(BBNode parent, boolean isLeft) {
		this.parent = parent;
		this.isLeftChild = isLeft;
	}
}
 
 /**
  * This internal class represent a node in MaxHeap;
  * @author wanyongquan
  *
  */
 static class HeapNode implements Comparable<HeapNode>{
	 BBNode liveNode; 
	 int upperLimitWeight;  // the upper limitation of live node;
	 int level;             // the node level in solution space tree 
	 
	 public HeapNode(BBNode node, int upLimit, int level) {
		 this.liveNode = node;
		 this.upperLimitWeight = upLimit;
		 this.level = level;
		 
	 }
	 public int compareTo(HeapNode otherNode) {
		 // notice the two params's order ;
		 // this will works as MaxHeap;
		 return Integer.compare( otherNode.upperLimitWeight, this.upperLimitWeight ) ;
			
	 }
	 public boolean equals(HeapNode item) {
		 return this.upperLimitWeight == ((HeapNode)item).upperLimitWeight;
	 }
 }
 
}


main方法中测试的结果如下图所示，可以最优装载量和解空间树最优选择路径都是正确的。

the best load weight is: 50 
the node path of best solution:	1	1	0

 

装载问题实质： 装载问题是一个子集选取问题，因此其解空间树是一颗子集树。
这里实现优先队列式分支限界法。
如果你在用优先队列时用less关键字，发现生成的并不是优先队列 参考https://blog.csdn.net/m0_38015368/article/details/80461938
#include <bits/stdc++.h>
using namespace std;
class MaxHeapQNode
{
public:
    MaxHeapQNode *parent;
    int lchild;
    int weight;
    int lev;
};
struct cmp
{
    bool operator()(MaxHeapQNode *&a, MaxHeapQNode *&b) const
    {
        return a->weight < b->weight;
    }
};
int n;
int c;
int bestw;
int w[100];
int bestx[100];
void InPut()
{
    scanf("%d %d", &n, &c);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &w[i]);
}
void AddAliveNode(priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp> &q, MaxHeapQNode *E,  int wt, int i, int ch)
{
    MaxHeapQNode *p = new MaxHeapQNode;
    p->parent = E;
    p->lchild = ch;
    p->weight = wt;
    p->lev = i + 1;
    q.push(p);
}
void MaxLoading()
{
    priority_queue<MaxHeapQNode *, vector<MaxHeapQNode *>, cmp > q; // 大顶堆
    //定义剩余重量数组r
    int r[n + 1];
    r[n] = 0;
    for(int j = n - 1; j > 0; --j)
        r[j] = r[j + 1] + w[j + 1];
    int i = 1;
    MaxHeapQNode *E;
    int Ew = 0;
    while(i != n + 1)
    {
        if(Ew + w[i] <= c)
        {
            AddAliveNode(q, E, Ew + w[i] + r[i], i, 1);
        }
        AddAliveNode(q, E, Ew + r[i], i, 0);

        //取下一节点
        E = q.top();
        q.pop();
        i = E->lev;
        Ew = E->weight - r[i - 1];
    }
    bestw = Ew;
    for(int j = n; j > 0; --j)
    {
        bestx[j] = E->lchild;
        E = E->parent;
    }
}
void OutPut()
{
    printf("最优装载量为 %d\n", bestw);
    printf("装载的物品为 \n");
    for(int i = 1; i <= n; ++i)
        if(bestx[i] == 1)
          printf("%d ", i);
}
int main()
{
    InPut();
    MaxLoading();
    OutPut();
}
测试样例：
输入：
(多解，输出其中一个）
4 60
10
40
50
20
输出
最优装载量为 60
装载的物品为
1 3
运行截图