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

一 、实验要求

1．要求用分支界限法求解0-1背包问题；

2．要求交互输入背包容量，物品重量数组，物品价值数组； 3．要求显示结果。

二 、实验仪器和软件平台

仪器 ：带usb接口微机

软件平台：WIN-XP + VC++6.0

三 、源程序

#include \#include #include #include #include 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

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

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->ubnext=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

cleft-=w[i]; b+=p[i]; i++; }

//装填剩余容量装满背包 if (i

//计算最优值和变量值 void Knap::display() { int i; cout<=1;i--) {

x[M[i-1]]=bestp->bag; bestp=bestp->parent; } cout<<\变量值 x = \ for(i=1;i<=n;i++) cout<

//背包问题求解

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); } }