- 1、本文档共7页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
分支界限法解0-1背包问题实验报告
实验5 分支界限法解0-1背包问题
一 、实验要求
要求用分支界限法求解0-1背包问题;
要求交互输入背包容量,物品重量数组,物品价值数组;
要求显示结果。
二 、实验仪器和软件平台
仪器 :带usb接口微机
软件平台:WIN-XP + VC++6.0
三 、源程序
#include stdafx.h
#includeiostream
#includecstdio
#includeconio.h
#includeiomanip
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;in;i++)
{
minl=1.0*p[i]/w[i];
k=0;
for(j=1;j=n-i;j++)
{
if(minl1.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;in;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
文档评论(0)