实验用分支限界法实现背包问题

一．实验目的

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

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

二．实验内容及要求

内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大? 要求：使用优先队列式分支限界法算法编程，求解0-1背包问题

三．程序列表

#include #include using namespace std; #define N 100

class HeapNode //定义HeapNode结点类 { public:

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

为结点所相应的重量 };

double MaxBound(int i); double Knap();

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

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

double w[N], p[N]; //把物品重量和价值定义为双精度浮点数 double cw, cp, c; //cw为当前重量，cp为当前价值，定义背包容量为c int n; //货物数量为 int main() { }

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

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 cleft = c - cw; //剩余容量 double b = cp; //价值上界

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

if (k <= n)

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

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) //左儿子结点为可行结点 { }

up = MaxBound(i + 1);

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

AddLiveNode(up, cp, cw, false, i + 1); if (cp + p[i]>bestp)

bestp = cp + p[i];

AddLiveNode(up, cp + p[i], cw + w[i], true, 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;

}

}四．实验结果