(C++)分支限界法求解背包问题

比眉伴天荒 2022-09-17 11:19 219阅读 0赞

1.beibao.h文件代码如下：

#ifndef BEIBAO_H
    #define  BEIBAO_H
    
    #include <math.h>
    
    
    //子空间中节点类型
    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

2.测试代码

#include <iostream>
    using namespace std;
    
    
    
    //子空间中节点类型
    #include "beibao.h"
    
    
    double c=30; 
    const int n=3;
    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;
    
    }
    
    
    
    
    void main(){
    	
    	w=new double[4];
    	w[1]=16;w[2]=15;w[3]=15;
    	p=new double[4];
    	p[1]=45;p[2]=25;p[3]=25;
    	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;
    }

3.测试结果：

*****分支限界法*****
    *****物品个数：n=3
    *****背包容量：c=30
    *****物品重量数组：w= {15 16 15}
    *****物品价值数组：v= {25 45 25}
    *****最优值：=50
    *****选中的物品是:0 1 1