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

Document serial number【KK89K-LLS98YT-SS8CB-SSUT-SST108】
实验用分支限界法实现背包问题
实验四 用分支限界法实现0-1背包问题
一．实验目的
。
。
二．实验内容及要求
内容：.给定n种物品和一个背包。物品i的重量是w，其价值为v，背包容量为c。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大
要求：使用优先队列式分支限界法算法编程，求解0-1背包问题
三．程序列表
#include<iostream>
#include<stack>
using namespace 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 -=