实验5 分支界限法解0-1背包问题
一、实验要求
1．要求用分支界限法求解0-1背包问题；
2．要求交互输入背包容量，物品重量数组，物品价值数组；
3．要求显示结果。
二、实验仪器和软件平台
仪器 ：带usb接口微机
软件平台：WIN-XP + VC++6.0
三、源程序
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<conio.h>
#include<iomanip>
using namespace std;
int *x;
struct node //结点表结点数据结构
{
node *parent;//父结点指针
node *next; //后继结点指针
int level;//结点的层
int bag;//节点的解
int cw;//当前背包装载量
int cp;//当前背包价值
float ub; //结点的上界值
};
//类Knap中的数据记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间
class Knap
{
private:
struct node *front, //队列队首
*bestp,*first; //解结点、根结点
int *p,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系
long lbestp;//背包容量最优解
public:
void Sort();
Knap(int *pp,int *ww,int cc,int nn);
~Knap();
float Bound(int i,int cw,int cp);//计算上界限
node *nnoder(node *pa,int ba,float uub);//生成一个结点 ba=1生成左节点 ba=0生成右节点
void addnode(node *nod);//向队列中添加活结点
void deletenode(node *nod);//将结点从队列中删除
struct node *nextnode(); //取下一个节点
void display(); //输出结果
void solvebag(); //背包问题求解
};
//按物品单位重量的价值排序
void Knap::Sort()
{
int i,j,k,kkl;
float minl;
for(i=1;i<n;i++)
{
minl=1.0*p[i]/w[i];
k=0;
for(j=1;j<=n-i;j++)
{
if(minl<1.0*p[j]/w[j])
{
minl=1.0*p[j]/w[j];
swap(p[k],p[j]);
swap(w[k],w[j]);
swap(M[k],M[j]);
k=j;
}
}
}
}
Knap::Knap(int *pp,int *ww,int cc,int nn)
{
int i;
n=nn;
c=cc;
p=new int[n];
w=new int[n];
M=new int[n];
for(i=0;i<n;i++)
{
p[i]=pp[i];
w[i]=ww[i];
M[i]=i; //用M数组记录大小顺序关系
}
front=new node[1];
front->next=NULL;
lbestp=0;
bestp=new node[1];
bestp=NULL;
Sort();
}
Knap::~Knap()
{
delete []first;
delete []front;
delete []bestp;
delete []p;
delete []w;
}
//取上限最大结点
node *Knap::nextnode()
{
node *p=front->next;
front->next=p->next;
return(p);
}
//将一个新的结点插入到子集树和优先队列中
node * Knap::nnoder(struct node *pa,int ba,float uub)
{//生成一个新结点
node * nodell=new(node);
nodell->parent=pa;
nodell->next=NULL;
nodell->level=(pa->level)+1;
nodell->bag=ba;
nodell->ub=uub;
if(ba==1)
{
nodell->cw=pa->cw+w[pa->level];
nodell->cp=pa->cp+p[pa->level] ;
}
else
{
nodell->cw=pa->cw;
nodell->cp=pa->cp;
}
return(nodell);
}
//将结点加入优先队列
void Knap::addnode(node *no)
{
node *p=front->next,*next1=front;
float ub=no->ub;
while(p!=NULL)
{
if(p->ub<ub){no->next=p;next1->next=no;break;}
next1=p;
p=p->next;
}
if(p==NULL){next1->next=no;}
}
// 计算结点所相应价值的上界
float Knap::Bound(int i,int cw,int cp)
{
int cleft=c-cw; //剩余容量
float b=(float)cp; //价值上界
//以物品单位重量价值减序装填剩余容量
while (i<n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//装填剩余容量装满背包
if (i<n) b+=1.0*p[i]/w[i]*cleft;
return b;
}
//计算最优值和变量值
void Knap::display()
{
int i;
cout<<endl;
cout<<"当前最优价值为:"<<lbestp<<endl;
for(i=n;i>=1;i--)
{
x[M[i-1]]=bestp->bag;
bestp=bestp->parent;
}
cout<<"变量值 x = ";
for(i=1;i<=n;i++)
cout<<x[i-1];
cout<<endl;
}
//背包问题求解
void Knap::solvebag()
{
int i;
float ubb;
node *aa; //记录上限最大结点
first=new node[1]; //根结点
first->parent=NULL;
first->next=NULL;
first->level=0; //用level记录结点的层
first->cw=0;
first->cp=0;
first->bag=0;
ubb=Bound(0,0,0);
first->ub=ubb;
front->next=first;
while(front->next!=NULL)
{
aa=nextnode();
i=aa->level;
//当叶子节点处的解>最优解时，更新最优解
if(i==n-1)
{
if(aa->cw+w[i]<=c&&(long)(aa->cp+p[i])>lbestp)
{
lbestp=aa->cp+p[i];
bestp=nnoder(aa,1,(float)lbestp);//将一个新的结点插入到子集树和优先队列中
}
if((long)(aa->cp)>lbestp)
{
lbestp=aa->cp;
bestp=nnoder(aa,0,(float)lbestp);
}
}
//非叶子结点，递归调用Bound函数计算上界
if(i<n-1)
{
if(aa->cw+w[i]<=c&&Bound(i+1,aa->cw+w[i],aa->cp+p[i])>(float)lbestp)
{
ubb=Bound(i,aa->cw+w[i],aa->cp+p[i]);
addnode(nnoder(aa,1,ubb));//将结点加入到优先队列中
}
ubb=ubb=Bound(i,aa->cw,aa->cp);
if(ubb>lbestp)
addnode(nnoder(aa,0,ubb));
}
}
display();
}
int main()
{
int c,n;
int i=0;
int *p;
int *w;
cout<<endl;
cout<<"|***********分支限界法解0-1背包问题***********| "<<endl;
cout<<endl;
cout<<"请输入物品数量 n = ";
cin>>n;
cout<<endl;
cout<<"请输入背包容量 C = ";
cin>>c;
cout<<endl;
x=new int[n]; //变量值
p=new int[n]; //物品价值
w=new int[n]; //物品重量
cout<<"请分别输入这"<<n<<"个物品的重量W:"<<endl;
for(i=0;i<n;i++)
cin>>w[i];
cout<<endl;
cout<<"请输入这"<<n<<"个物品的价值P:"<<endl;
for(i=0;i<n;i++)
cin>>p[i];
Knap knbag(p,w,c,n);
knbag.solvebag();
getch();
return 0;
}
四、运行结果
五、实验小结
回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
第二篇：利用分枝界限法求解0-1背包问题
//文件名：BAGPROBLEM.cpp//功能：利用分枝界限法求解0-1背包问题#include <iostream>using namespace std;#define e 0.0001struct NODE{ //结点数据结构NODE *Parent; //指向父结点指针NODE *next; //后继结点指针int Level; //结点的所在的层数int Tag; //左右孩子的标志，1为左孩子，0为右孩子int CW; //目前背包剩余空间int CV; //目前已装入物品有效益值int LB; //结点的下界值float UB; //结点的上界值};NODE *head; //活动结点队列队头NODE *RESULT,*E; //解结点、根结点int *v,*w; //指向物品的价值、重量数组指针int W,lb,cw,cv; //背包最大容量、下限、目前剩余容量、目前物品价值之和int N; //背包中物品数量float ub; //背包的价值上限void INIT(int *vv,int *ww,int WW,int NN,int& value); //初始化队列void LUBOUND(int rw,int cp,int k,int &LBB,float &UBB); //计算上下界限NODE* INSERTNODE(NODE *parent,int level,int t,int cw,int cv,int lb,float ub); //生成一个新结点void ENQUEUE(NODE *node); //将结点i加入优先队列void DEQUEUE(NODE *node); //将结点i从优先队列中删除(杀死结点)NODE* NEXLIVENODE(); //下一扩展结点(取下限lb最大结点)void PRINT(NODE* result,int n,int value); //打印结果void LCBB(NODE* reusult,int n,int W,int lb,float ub,int cv,int cw,int& value); //求解最优解int main(){int VALUE; //目前装入物品价值int value[]={20,20,24,36}; int weight[]={10,20,30,45};int BW;cout<<"各个物品的价值和重量为："<<endl;cout<<"name\tvalue\tweight"<<endl;for(int i=0;i<sizeof(value)/sizeof(int);i++)cout<<"x"<<i+1<<"\t"<<value[i]<<"\t"<<weight[i]<<endl;cout << "请输入背包的重量:";cin >> BW;cout << endl;INIT(value,weight,BW,sizeof(value)/sizeof(int),VALUE);LCBB(RESULT,N,W,lb,ub,cv,cw,VALUE);return 0;}void INIT(int *vv,int *ww,int WW,int NN,int& value) //初始化队列{N=NN;W=WW;v=new int[N];w=new int[N];for(int i=0;i<N;i++){v[i]=vv[i];w[i]=ww[i];}head=new(NODE);head->next=NULL;value=0;RESULT=new(NODE);}void LUBOUND(int rw,int cp,int k,int &LBB,float &UBB) //计算上下界限{int i,j,c;LBB=cp;c=rw;for(i=k;i<N;i++){if(c<w[i]){UBB=(float)(LBB+c*v[i]/w[i]);for(j=i+1;j<N;j++)if(c>=w[j]){c=c-w[j];LBB+=v[j];}return;}c=c-w[i];LBB+=v[i];}UBB=(float)LBB;}NODE* INSERTNODE(NODE *parent,int level,int t,int cw,int cv,int lb,float ub) //生成一个新结点{NODE* node=new(NODE);node->Parent=parent;node->next=NULL;node->Level=level;node->Tag=t;node->CW=cw;node->CV=cv;node->UB=ub;node->LB=lb;return(node);}v
oid ENQUEUE(NODE* node) //将结点i加入优先队列{node->next=head->next;head->next=node;}void DEQUEUE(NODE* node) //将结点i从优先队列中删除{NODE *pre=head,*p=head->next;while(p!=node){pre=p;p=p->next;}pre->next=p->next;}NODE* NEXLIVENODE() //下一扩展结点(取下限lb最大结点){NODE *p=head->next,*choice=p;int lb=p->LB;while(p){if(p->LB>lb)choice=p;p=p->next;}return(choice);}void PRINT(NODE* result,int n,int value) //打印结果{cout<<"背包装入的最大价值为:"<<value<<endl;cout<<"装入包中的物品有:";for(int i=n;i>=1;i--){if(RESULT->Tag==1)cout<<'x'<<i<<' ';RESULT=RESULT->Parent;}cout<<endl;}void LCBB(NODE* reusult,int n,int W,int lb,float ub,int cv,int cw,int& value) //求解最优解{int i;NODE* node=new(NODE); //根结点node->Parent=NULL;node->next=NULL;node->Level=0;node->CW=W;node->CV=0;node->Tag=0;LUBOUND(W,0,0,lb,ub); //计算根结点上下界限value=lb-e;node->LB=lb;node->UB=ub;while(node->UB>value) //当前扩展结点上界<当前解时结束{i=node->Level;cw=node->CW;cv=node->CV;if(i==N){if(cv>value){value=cv;RESULT=node;}}else //node有两个儿子{ if(cw>=w[i]) //左孩子结点可行ENQUEUE(INSERTNODE(node,i+1,1,cw-w[i],cv+v[i],node->LB,node->UB));LUBOUND(cw,cv,i+1,lb,ub); //重新计算上下界if(ub>value) //右孩子结点可行{ ENQUEUE(INSERTNODE(node,i+1,0,cw,cv,lb,ub));if(value<lb-e)value=lb-e;}}if(head->next==NULL) //队列空或ub>VALUE结束break;else{node=NEXLIVENODE(); //下一扩展结点DEQUEUE(node); //将结点从队列中删除}}PRINT(RESULT,n,value);}