实验四用分支限界法实现0-1背包问题

一．实验目的

1.熟悉分支限界法的基本原理。

2.通过本次实验加深对分支限界法的理解。

二．实验内容及要求

内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大?

要求：使用优先队列式分支限界法算法编程，求解0-1背包问题

三．程序列表

#include<iostream>

#include<stack>

usingnamespace std;

#define N 100

class HeapNode//定义HeapNode结点类

{

public:

double upper, price, weight; //upper为结点的价值上界，price是结点所对应的价值，weight 为结点所相应的重量

int level, x[N]; //活节点在子集树中所处的层序号

};

double MaxBound(int i);

double Knap();

void AddLiveNode(double up, double cp, double cw, bool ch, int level);//up是价值上界，cp是相应的价值，cw是该结点所相应的重量，ch是ture or false

stack<HeapNode> High; //最大队High

double w[N], p[N]; //把物品重量和价值定义为双精度浮点数

double cw, cp, c; //cw为当前重量，cp为当前价值，定义背包容量为c

int n; //货物数量为

int main()

{

cout <<"请输入背包容量："<< endl;

cin >> c;

cout <<"请输入物品的个数："<< endl;

cin >> n;

cout <<"请按顺序分别输入物品的重量："<< endl;

int i;

for (i = 1; i <= n; i++)

cin >> w[i]; //输入物品的重量

cout <<"请按顺序分别输入物品的价值："<< endl;

for (i = 1; i <= n; i++)

cin >> p[i]; //输入物品的价值

cout <<"最优值为：";

cout << Knap() << endl; //调用knap函数输出最大价值

return 0;

}

double MaxBound(int k) //MaxBound函数求最大上界

{

double cleft = c - cw; //剩余容量

double b = cp; //价值上界

while (k<= n&&w[k] <= cleft) //以物品单位重量价值递减装填剩余容量

{

cleft -= w[k];

b += p[k];

k++;

}

if (k<= n)

b += p[k] / w[k] * cleft; //装填剩余容量装满背包

return b;

}

void AddLiveNode(double up, double cp, double cw, bool ch, int lev) //将一个新的活结点插入到子集数和最大堆High中

{

HeapNode be;

be.upper = up;

be.price = cp;

be.weight = cw;

be.level = lev;

if (lev<= n)

High.push(be);

}//调用stack头文件的push函数 }

double Knap() //优先队列分支限界法，返回最大价值，bestx返回最优解

{

int i = 1;

cw = cp = 0;

double bestp = 0; //best为当前最优值

double up = MaxBound(1);//价值上界

//搜索子集空间树

while (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], true, i + 1);

}

up = MaxBound(i + 1);

if (up >= bestp) //右子数可能含最优解

AddLiveNode(up, cp, cw, false, i + 1);

if (High.empty())

return bestp;

HeapNode node = High.top(); //取下一扩展结点

High.pop();

cw = node.weight;

cp = node.price;

up = node.upper;

i = node.level;

}

}四．实验结果