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

实验四用分支限界法实现0-1背包问题
实验目的
熟悉分支限界法的基本原理。
通过本次实验加深对分支限界法的理解。
实验内容及要求
内容：•给定n种物品和一个背包。物品i的重量是w,其价值为v，背包容量为 c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大 ？
要求：使用优先队列式分支限界法算法编程，求解 0-1背包问题
程序列表
#inelude <iostream>
#include <stack>
using namespacestd;
#defi ne N 100
class HeapNode // 定义 HeapNode结点类
{
public :
double upper, price, weight; //upper 为结点的价值上界，price 是结点所对应的价值， weight
为结点所相应的重量
int level, x[ N]; //活节点在子集树中所处的层序号
};
double MaxBound(int i);
double Kn ap();
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; // 剩余容量
{
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中
HeapNodebe;
b