优先队列式分支限界法求解0-1背包问题

建站810 更新时间：2025-06-08 12:28:17

2023年8月1日发(作者：)

算法分析与设计实验报告

第 7 次实验

姓名

时间

实验名称

6.4上午

学号

地点四合院

班级

优先队列式分支限界法求解0-1背包问题

通过上机实验，要求掌握优先队列式分支限界法求解0-1背包问题的问题描述、算法设计思想、程序设计。

1、使用优先队列式分支限界法算法，根据不同的输入用例，能准确的输出背包能装的最大价值，并计算出程序运行所需要的时间。

2、分支限界法常以广度优先或最小耗费优先（最大效益优先）方式搜索问题的解空间树，对于0-1背包问题的解空间树是一个棵子集树。

实验目的

3、在分支限界法中有一个活结点表，活结点表中的每个活结点只有一次机会成为扩实验原理

展结点，一旦成为扩展结点就一次性产生所有儿子结点，在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。

4、为了尽快找到0-1背包问题的解，每次选取下一个活结点成为扩展结点的判断依据是当前情况下最有可能找到最优解的下一个结点。因此，每次选择扩展结点的方法：当前情况下，在活结点表中选择活结点的上界，最大的活结点成为当前的扩展结点。

这一过程一直持续到找到所需的解或活结点表为空时为止。

1、定义树结点类bbnode，用于构造子集树，以便计算最优解；定义堆结点类HeapNode，用于定义堆元素类型；定义最大堆类MaxHeap，用于实现优先队列定义.物品类Object，用于保存物品编号和物品的单位重量价值；定义解决0-1背包问题的主类Knap。

实验步骤

2、设计求解0-1背包问题的主函数Knapsack，在其中对物品以单位价值量排序。

3、设计负责求解0-1背包问题的最优值和最优解函数MaxKnapsack在其中调用计算结点价值上界函数Bound，向子集树和最大堆中插入结点函数AddLiveNode和释放最大堆最大结点的函数DeleteMax，实现优先级队列。

4、输入数据到文件中。

5、添加计算运行时间的代码，计算不同规模数据的运行时间，并将结果输出到output文件中。

6、分析时间复杂度：在最坏的情况下所有的节点都入队，最后一个节点才是最优解，这种情况下时间复杂度是指数阶。最好的情况是只装单位价值最大的物品，其余分支都不符合条件被截去这种情况下时间复杂度是常数时间。但分支限界法本质上还是穷举法，平均时间复杂度仍是指数阶。关键代码

//物品类

class Object{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

int operator <= (Object a) const{

return (d >= a.d);

}

private:

int ID; //物品编号

float d; //单位重量价值

};

//树结点类

class bbnode{

friend class Knap;

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

private:

bbnode *parent; //指向父节点的指针

int LChild;

};

//堆结点类

class HeapNode{

friend class Knap;

friend class MaxHeap;

public:

operator Typep()const{return uprofit;};

private:

Typep uprofit, //结点的价值上界

profit; //结点所相应的价值

Typew weight; //结点所相应的重量

int level; //活结点在子集树中所处的层序号

bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针

};

//最大堆类

class MaxHeap{

public:

MaxHeap(int maxElem)

{

HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留

capacity = maxElem;

size = 0; }

void InsertMax(HeapNode *newNode);

HeapNode DeleteMax(HeapNode* &N);

private:

int capacity;

int size;

HeapNode **HeapElem;

};

//0-1背包问题的主类

class Knap{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

Typep MaxKnapsack();

private:

MaxHeap *H;

Typep Bound(int i);

void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level);

bbnode *E; //指向扩展结点的指针

Typew c; //背包容量

int n; //物品总数

Typew *w; //物品重量数组（以单位重量价值降序）

Typep *p; //物品价值数组（以单位重量价值降序）

Typew cw; //当前装包重量

Typep cp; //当前装包价值

int *bestx; //最优解

};

void MaxHeap::InsertMax(HeapNode *newNode)

{

int i = 1;

for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit;

i /= 2)

{

HeapElem[i] = HeapElem[i/2];

}

HeapElem[i] = newNode;

}

HeapNode MaxHeap::DeleteMax(HeapNode *&N)

{

if(size >0 ) {

N = HeapElem[1];

int i = 1;

while(i < size)

{

if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit >

HeapElem[i*2 +1]->uprofit)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

{

if(i*2 <= size)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

break;

}

if(i < size)

HeapElem[i] = HeapElem[size];

}

size--;

return *N;

}

Typep Knap::MaxKnapsack()

{

H = new MaxHeap(10000);

bestx = new int [n+1];

int i = 1;

E = 0;

cw = 0;

cp = 0;

Typep bestp = 0;

Typep up = Bound(1);

while (i != n+1)

{

Typew wt = cw + w[i];

if(wt <= c) {

if(cp + p[i] > bestp) bestp = cp + p[i];

AddLiveNode(up, cp + p[i], cw + w[i], 1, i);

}

up = Bound(i + 1);

if(up >= bestp)

AddLiveNode(up, cp, cw, 0, i);

HeapNode* N;

H->DeleteMax(N);

E = N->elemPtr;

cw = N->weight;

cp = N->profit;

up = N->uprofit;

i = N->level + 1;

}

for (int i = n; i > 0; i--)

{

bestx[i] = E->LChild;

E = E->parent;

}

return cp;

}

Typep Knap::Bound(int i)

{

Typew cleft = c - cw;

Typep b = cp;

while (i<=n && w[i] <= cleft)

{

cleft -= w[i];

b += p[i];

i++;

}

if(i<=n) b += p[i]/w[i] * cleft;

return b;

}

void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level)

{

bbnode *b=new bbnode;

b->parent=E;

b->LChild=ch;

HeapNode *N = new HeapNode;

N->uprofit=up; N->profit=cp;

N->weight=cw;

N->level=level;

N->elemPtr=b;

H->InsertMax(N);

}

//Knapsack返回最大价值，最优值保存在bestx

Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx)

{

Typew W = 0;

Typep P = 0;

Object *Q = new Object[n];

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

{

Q[i-1].ID = i;

Q[i-1].d = 1.0*p[i]/w[i];

P += p[i];

W += w[i];

}

if (W <= c)

{

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

{

bestx[i] = p[i];

}

return P;

}

for(int i = 1; i

for(int j = 1; j<= n-i; j++)

{

if(Q[j-1].d < Q[j].d)

{

Object temp = Q[j-1];

Q[j-1] = Q[j];

Q[j] = temp;

}

Knap K;

K.p = new Typep [n+1];

K.w = new Typew [n+1];

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

{ K.p[i] = p[Q[i-1].ID];

K.w[i] = w[Q[i-1].ID];

}

= 0;

K.c = c;

K.n = n;

Typep bestp = psack();

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

{

bestx[Q[i-1].ID] = [i];

}

delete [] Q;

delete [] K.w;

delete [] K.p;

delete [] ;

delete [] K.H;

return bestp;

}

1、测试自己输入的小规模数据

测试结果

2、测试随机生成100

3、随机生成1000数据

4、随机生成1000数据

在做本次实验之前，我对分支限界法的原理并不是很理解，经过查看课件及网上查找资料，同时结合自己对回溯法等的理解，我对分支限界法有了一个较好的理解，知道了两种主要的分支限界法及分支限界法如何应用于解01背包问题。在查找资料的过程中，我查看了许多网上的别人的代码实现，结合课本上的代码完成了该实验。通过本次试验，我基本上掌握了优先队列分支限界法解0-1背包问题的原理，同时锻炼了自己动手编写及调试代码的能力，收获实验心得良多。

实验得分助教签名

附录：完整代码

#include

using namespace std;

ifstream in("");

ofstream out("");

typedef int Typew;

typedef int Typep;

//物品类

class Object{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

int operator <= (Object a) const{

return (d >= a.d);

}

private:

int ID; //物品编号

float d; //单位重量价值

};

//树结点类

class bbnode{

friend class Knap;

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

private:

bbnode *parent; //指向父节点的指针

int LChild;

};

//堆结点类

class HeapNode{

friend class Knap;

friend class MaxHeap; public:

operator Typep()const{return uprofit;};

private:

Typep uprofit, //结点的价值上界

profit; //结点所相应的价值

Typew weight; //结点所相应的重量

int level; //活结点在子集树中所处的层序号

bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针

};

//最大堆类

class MaxHeap{

public:

MaxHeap(int maxElem)

{

HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留

capacity = maxElem;

size = 0;

}

void InsertMax(HeapNode *newNode);

HeapNode DeleteMax(HeapNode* &N);

private:

int capacity;

int size;

HeapNode **HeapElem;

};

//0-1背包问题的主类

class Knap{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

Typep MaxKnapsack();

private:

MaxHeap *H;

Typep Bound(int i);

void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level);

bbnode *E; //指向扩展结点的指针

Typew c; //背包容量

int n; //物品总数

Typew *w; //物品重量数组（以单位重量价值降序）

Typep *p; //物品价值数组（以单位重量价值降序）

Typew cw; //当前装包重量 Typep cp; //当前装包价值

int *bestx; //最优解

};

void MaxHeap::InsertMax(HeapNode *newNode)

{

int i = 1;

for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit; i /= 2)

{

HeapElem[i] = HeapElem[i/2];

}

HeapElem[i] = newNode;

}

HeapNode MaxHeap::DeleteMax(HeapNode *&N)

{

if(size >0 )

{

N = HeapElem[1];

int i = 1;

while(i < size)

{

if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit >

+1]->uprofit)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

{

if(i*2 <= size)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

break;

}

if(i < size)

HeapElem[i] = HeapElem[size];

}

size--;

return *N;

HeapElem[i*2 }

Typep Knap::MaxKnapsack()

{

H = new MaxHeap(10000);

bestx = new int [n+1];

int i = 1;

E = 0;

cw = 0;

cp = 0;

Typep bestp = 0;

Typep up = Bound(1);

while (i != n+1)

{

Typew wt = cw + w[i];

if(wt <= c) {

if(cp + p[i] > bestp)

bestp = cp + p[i];

AddLiveNode(up, cp + p[i], cw + w[i], 1, i);

}

up = Bound(i + 1);

if(up >= bestp)

AddLiveNode(up, cp, cw, 0, i);

HeapNode* N;

H->DeleteMax(N);

E = N->elemPtr;

cw = N->weight;

cp = N->profit;

up = N->uprofit;

i = N->level + 1;

}

for (int i = n; i > 0; i--)

{

bestx[i] = E->LChild;

E = E->parent;

}

return cp;

}

Typep Knap::Bound(int i)

{

Typew cleft = c - cw;

Typep b = cp; while (i<=n && w[i] <= cleft)

{

cleft -= w[i];

b += p[i];

i++;

}

if(i<=n) b += p[i]/w[i] * cleft;

return b;

}

void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level)

{

bbnode *b=new bbnode;

b->parent=E;

b->LChild=ch;

HeapNode *N = new HeapNode;

N->uprofit=up;

N->profit=cp;

N->weight=cw;

N->level=level;

N->elemPtr=b;

H->InsertMax(N);

}

//Knapsack返回最大价值，最优值保存在bestx

Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx)

{

Typew W = 0;

Typep P = 0;

Object *Q = new Object[n];

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

{

Q[i-1].ID = i;

Q[i-1].d = 1.0*p[i]/w[i];

P += p[i];

W += w[i];

}

if (W <= c)

{

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

{

bestx[i] = p[i];

}

return P; }

for(int i = 1; i

for(int j = 1; j<= n-i; j++)

{

if(Q[j-1].d < Q[j].d)

{

Object temp = Q[j-1];

Q[j-1] = Q[j];

Q[j] = temp;

}

Knap K;

K.p = new Typep [n+1];

K.w = new Typew [n+1];

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

{

K.p[i] = p[Q[i-1].ID];

K.w[i] = w[Q[i-1].ID];

}

= 0;

K.c = c;

K.n = n;

Typep bestp = psack();

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

{

bestx[Q[i-1].ID] = [i];

}

delete [] Q;

delete [] K.w;

delete [] K.p;

delete [] ;

delete [] K.H;

return bestp;

}

int main()

{

cout<<"请在文件中输入物品数量、背包容量"<

int N ;

in>>N;

Typew c; //背包容量

in>>c;

int bestx[N+1]; //最优解 int bestp; //最优值

Typep p[N+1];//物品价值

Typew w[N+1];//物品重量

cout<<"在文件中读取的物品总数N = "<< N<<",背包容量C = "<< c<

cout<<"请选择生成数据的规模大小：200请输入1,2000请输入2，20000请输入3"<

int x;

cin>>x;

if(x==1)

{

ofstream in1("");

srand(time(NULL));

int n=200;

int *a=new int[n];

for(int i=0;i

{

a[i]=rand()%91;

in1<

}

cout<<"随机数已请生成到input1文件中，请将数据添加到文件中"<

}

else if(x==2)

{

ofstream in1("");

srand(time(NULL));

int n=2000;

int *a=new int[n];

for(int i=0;i

{

a[i]=rand()%91;

in1<

}

cout<<"随机数已请生成到input1文件中，请将数据添加到文件中"<

}

else if(x==3)

{

ofstream in1("");

srand(time(NULL));

int n=20000;

int *a=new int[n];

for(int i=0;i

{

a[i]=rand()%91;

in1<

} cout<<"随机数已请生成到input1文件中，请将数据添加到文件中"<

}

cout<<"添加完毕后请输入1"<

int m;

cin>>m;

clock_t start,finish;

start=clock();

for (int i = 1; i <= N; i++)

{

in>>w[i];

}

for (int i = 1; i <= N; i++)

{

in>>p[i];

}

cout<<"已在input文件中读取物品重量和价值。"<

bestp = Knapsack(w, p, c, N, bestx);

for (int i = 1; i <= N; i++)

{

if(i ==1 ) out<<"是否选取：";

out<

if(i != N) out<<",";

else

out<

}

out<<"背包最优价值："<

finish=clock();

out<<"开始时间为:"<

cout<<"结果已生成在文件中"<

system("pause");

return 0;

}

2023年8月1日发(作者：)

算法分析与设计实验报告

第 7 次实验

姓名

时间

实验名称

6.4上午

学号

地点四合院

班级

优先队列式分支限界法求解0-1背包问题

通过上机实验，要求掌握优先队列式分支限界法求解0-1背包问题的问题描述、算法设计思想、程序设计。

1、使用优先队列式分支限界法算法，根据不同的输入用例，能准确的输出背包能装的最大价值，并计算出程序运行所需要的时间。

2、分支限界法常以广度优先或最小耗费优先（最大效益优先）方式搜索问题的解空间树，对于0-1背包问题的解空间树是一个棵子集树。

实验目的

3、在分支限界法中有一个活结点表，活结点表中的每个活结点只有一次机会成为扩实验原理

展结点，一旦成为扩展结点就一次性产生所有儿子结点，在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。

4、为了尽快找到0-1背包问题的解，每次选取下一个活结点成为扩展结点的判断依据是当前情况下最有可能找到最优解的下一个结点。因此，每次选择扩展结点的方法：当前情况下，在活结点表中选择活结点的上界，最大的活结点成为当前的扩展结点。

这一过程一直持续到找到所需的解或活结点表为空时为止。

1、定义树结点类bbnode，用于构造子集树，以便计算最优解；定义堆结点类HeapNode，用于定义堆元素类型；定义最大堆类MaxHeap，用于实现优先队列定义.物品类Object，用于保存物品编号和物品的单位重量价值；定义解决0-1背包问题的主类Knap。

实验步骤

2、设计求解0-1背包问题的主函数Knapsack，在其中对物品以单位价值量排序。

3、设计负责求解0-1背包问题的最优值和最优解函数MaxKnapsack在其中调用计算结点价值上界函数Bound，向子集树和最大堆中插入结点函数AddLiveNode和释放最大堆最大结点的函数DeleteMax，实现优先级队列。

4、输入数据到文件中。

5、添加计算运行时间的代码，计算不同规模数据的运行时间，并将结果输出到output文件中。

6、分析时间复杂度：在最坏的情况下所有的节点都入队，最后一个节点才是最优解，这种情况下时间复杂度是指数阶。最好的情况是只装单位价值最大的物品，其余分支都不符合条件被截去这种情况下时间复杂度是常数时间。但分支限界法本质上还是穷举法，平均时间复杂度仍是指数阶。关键代码

//物品类

class Object{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

int operator <= (Object a) const{

return (d >= a.d);

}

private:

int ID; //物品编号

float d; //单位重量价值

};

//树结点类

class bbnode{

friend class Knap;

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

private:

bbnode *parent; //指向父节点的指针

int LChild;

};

//堆结点类

class HeapNode{

friend class Knap;

friend class MaxHeap;

public:

operator Typep()const{return uprofit;};

private:

Typep uprofit, //结点的价值上界

profit; //结点所相应的价值

Typew weight; //结点所相应的重量

int level; //活结点在子集树中所处的层序号

bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针

};

//最大堆类

class MaxHeap{

public:

MaxHeap(int maxElem)

{

HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留

capacity = maxElem;

size = 0; }

void InsertMax(HeapNode *newNode);

HeapNode DeleteMax(HeapNode* &N);

private:

int capacity;

int size;

HeapNode **HeapElem;

};

//0-1背包问题的主类

class Knap{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

Typep MaxKnapsack();

private:

MaxHeap *H;

Typep Bound(int i);

void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level);

bbnode *E; //指向扩展结点的指针

Typew c; //背包容量

int n; //物品总数

Typew *w; //物品重量数组（以单位重量价值降序）

Typep *p; //物品价值数组（以单位重量价值降序）

Typew cw; //当前装包重量

Typep cp; //当前装包价值

int *bestx; //最优解

};

void MaxHeap::InsertMax(HeapNode *newNode)

{

int i = 1;

for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit;

i /= 2)

{

HeapElem[i] = HeapElem[i/2];

}

HeapElem[i] = newNode;

}

HeapNode MaxHeap::DeleteMax(HeapNode *&N)

{

if(size >0 ) {

N = HeapElem[1];

int i = 1;

while(i < size)

{

if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit >

HeapElem[i*2 +1]->uprofit)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

{

if(i*2 <= size)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

break;

}

if(i < size)

HeapElem[i] = HeapElem[size];

}

size--;

return *N;

}

Typep Knap::MaxKnapsack()

{

H = new MaxHeap(10000);

bestx = new int [n+1];

int i = 1;

E = 0;

cw = 0;

cp = 0;

Typep bestp = 0;

Typep up = Bound(1);

while (i != n+1)

{

Typew wt = cw + w[i];

if(wt <= c) {

if(cp + p[i] > bestp) bestp = cp + p[i];

AddLiveNode(up, cp + p[i], cw + w[i], 1, i);

}

up = Bound(i + 1);

if(up >= bestp)

AddLiveNode(up, cp, cw, 0, i);

HeapNode* N;

H->DeleteMax(N);

E = N->elemPtr;

cw = N->weight;

cp = N->profit;

up = N->uprofit;

i = N->level + 1;

}

for (int i = n; i > 0; i--)

{

bestx[i] = E->LChild;

E = E->parent;

}

return cp;

}

Typep Knap::Bound(int i)

{

Typew cleft = c - cw;

Typep b = cp;

while (i<=n && w[i] <= cleft)

{

cleft -= w[i];

b += p[i];

i++;

}

if(i<=n) b += p[i]/w[i] * cleft;

return b;

}

void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level)

{

bbnode *b=new bbnode;

b->parent=E;

b->LChild=ch;

HeapNode *N = new HeapNode;

N->uprofit=up; N->profit=cp;

N->weight=cw;

N->level=level;

N->elemPtr=b;

H->InsertMax(N);

}

//Knapsack返回最大价值，最优值保存在bestx

Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx)

{

Typew W = 0;

Typep P = 0;

Object *Q = new Object[n];

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

{

Q[i-1].ID = i;

Q[i-1].d = 1.0*p[i]/w[i];

P += p[i];

W += w[i];

}

if (W <= c)

{

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

{

bestx[i] = p[i];

}

return P;

}

for(int i = 1; i

for(int j = 1; j<= n-i; j++)

{

if(Q[j-1].d < Q[j].d)

{

Object temp = Q[j-1];

Q[j-1] = Q[j];

Q[j] = temp;

}

Knap K;

K.p = new Typep [n+1];

K.w = new Typew [n+1];

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

{ K.p[i] = p[Q[i-1].ID];

K.w[i] = w[Q[i-1].ID];

}

= 0;

K.c = c;

K.n = n;

Typep bestp = psack();

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

{

bestx[Q[i-1].ID] = [i];

}

delete [] Q;

delete [] K.w;

delete [] K.p;

delete [] ;

delete [] K.H;

return bestp;

}

1、测试自己输入的小规模数据

测试结果

2、测试随机生成100

3、随机生成1000数据

4、随机生成1000数据

在做本次实验之前，我对分支限界法的原理并不是很理解，经过查看课件及网上查找资料，同时结合自己对回溯法等的理解，我对分支限界法有了一个较好的理解，知道了两种主要的分支限界法及分支限界法如何应用于解01背包问题。在查找资料的过程中，我查看了许多网上的别人的代码实现，结合课本上的代码完成了该实验。通过本次试验，我基本上掌握了优先队列分支限界法解0-1背包问题的原理，同时锻炼了自己动手编写及调试代码的能力，收获实验心得良多。

实验得分助教签名

附录：完整代码

#include

using namespace std;

ifstream in("");

ofstream out("");

typedef int Typew;

typedef int Typep;

//物品类

class Object{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

int operator <= (Object a) const{

return (d >= a.d);

}

private:

int ID; //物品编号

float d; //单位重量价值

};

//树结点类

class bbnode{

friend class Knap;

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

private:

bbnode *parent; //指向父节点的指针

int LChild;

};

//堆结点类

class HeapNode{

friend class Knap;

friend class MaxHeap; public:

operator Typep()const{return uprofit;};

private:

Typep uprofit, //结点的价值上界

profit; //结点所相应的价值

Typew weight; //结点所相应的重量

int level; //活结点在子集树中所处的层序号

bbnode *elemPtr; //指向该活结点在子集树中相应结点的指针

};

//最大堆类

class MaxHeap{

public:

MaxHeap(int maxElem)

{

HeapElem = new HeapNode* [maxElem+1]; //下标为0的保留

capacity = maxElem;

size = 0;

}

void InsertMax(HeapNode *newNode);

HeapNode DeleteMax(HeapNode* &N);

private:

int capacity;

int size;

HeapNode **HeapElem;

};

//0-1背包问题的主类

class Knap{

friend Typep Knapsack(Typew *, Typep *, Typew, int, int *);

public:

Typep MaxKnapsack();

private:

MaxHeap *H;

Typep Bound(int i);

void AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level);

bbnode *E; //指向扩展结点的指针

Typew c; //背包容量

int n; //物品总数

Typew *w; //物品重量数组（以单位重量价值降序）

Typep *p; //物品价值数组（以单位重量价值降序）

Typew cw; //当前装包重量 Typep cp; //当前装包价值

int *bestx; //最优解

};

void MaxHeap::InsertMax(HeapNode *newNode)

{

int i = 1;

for (i = ++size; i/2 > 0 && HeapElem[i/2]->uprofit < newNode->uprofit; i /= 2)

{

HeapElem[i] = HeapElem[i/2];

}

HeapElem[i] = newNode;

}

HeapNode MaxHeap::DeleteMax(HeapNode *&N)

{

if(size >0 )

{

N = HeapElem[1];

int i = 1;

while(i < size)

{

if(((i*2 +1) <= size) && HeapElem[i*2]->uprofit >

+1]->uprofit)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

{

if(i*2 <= size)

{

HeapElem[i] = HeapElem[i*2];

i = i*2;

}

else

break;

}

if(i < size)

HeapElem[i] = HeapElem[size];

}

size--;

return *N;

HeapElem[i*2 }

Typep Knap::MaxKnapsack()

{

H = new MaxHeap(10000);

bestx = new int [n+1];

int i = 1;

E = 0;

cw = 0;

cp = 0;

Typep bestp = 0;

Typep up = Bound(1);

while (i != n+1)

{

Typew wt = cw + w[i];

if(wt <= c) {

if(cp + p[i] > bestp)

bestp = cp + p[i];

AddLiveNode(up, cp + p[i], cw + w[i], 1, i);

}

up = Bound(i + 1);

if(up >= bestp)

AddLiveNode(up, cp, cw, 0, i);

HeapNode* N;

H->DeleteMax(N);

E = N->elemPtr;

cw = N->weight;

cp = N->profit;

up = N->uprofit;

i = N->level + 1;

}

for (int i = n; i > 0; i--)

{

bestx[i] = E->LChild;

E = E->parent;

}

return cp;

}

Typep Knap::Bound(int i)

{

Typew cleft = c - cw;

Typep b = cp; while (i<=n && w[i] <= cleft)

{

cleft -= w[i];

b += p[i];

i++;

}

if(i<=n) b += p[i]/w[i] * cleft;

return b;

}

void Knap::AddLiveNode(Typep up, Typep cp, Typew cw, int ch, int level)

{

bbnode *b=new bbnode;

b->parent=E;

b->LChild=ch;

HeapNode *N = new HeapNode;

N->uprofit=up;

N->profit=cp;

N->weight=cw;

N->level=level;

N->elemPtr=b;

H->InsertMax(N);

}

//Knapsack返回最大价值，最优值保存在bestx

Typep Knapsack(Typew *w, Typep *p, Typew c, int n, int *bestx)

{

Typew W = 0;

Typep P = 0;

Object *Q = new Object[n];

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

{

Q[i-1].ID = i;

Q[i-1].d = 1.0*p[i]/w[i];

P += p[i];

W += w[i];

}

if (W <= c)

{

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

{

bestx[i] = p[i];

}

return P; }

for(int i = 1; i

for(int j = 1; j<= n-i; j++)

{

if(Q[j-1].d < Q[j].d)

{

Object temp = Q[j-1];

Q[j-1] = Q[j];

Q[j] = temp;

}

Knap K;

K.p = new Typep [n+1];

K.w = new Typew [n+1];

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

{

K.p[i] = p[Q[i-1].ID];

K.w[i] = w[Q[i-1].ID];

}

= 0;

K.c = c;

K.n = n;

Typep bestp = psack();

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

{

bestx[Q[i-1].ID] = [i];

}

delete [] Q;

delete [] K.w;

delete [] K.p;

delete [] ;

delete [] K.H;

return bestp;

}

int main()

{

cout<<"请在文件中输入物品数量、背包容量"<

int N ;

in>>N;

Typew c; //背包容量

in>>c;

int bestx[N+1]; //最优解 int bestp; //最优值

Typep p[N+1];//物品价值

Typew w[N+1];//物品重量

cout<<"在文件中读取的物品总数N = "<< N<<",背包容量C = "<< c<

cout<<"请选择生成数据的规模大小：200请输入1,2000请输入2，20000请输入3"<

int x;

cin>>x;

if(x==1)

{

ofstream in1("");

srand(time(NULL));

int n=200;

int *a=new int[n];

for(int i=0;i

{

a[i]=rand()%91;

in1<

}

cout<<"随机数已请生成到input1文件中，请将数据添加到文件中"<

}

else if(x==2)

{

ofstream in1("");

srand(time(NULL));

int n=2000;

int *a=new int[n];

for(int i=0;i

{

a[i]=rand()%91;

in1<

}

cout<<"随机数已请生成到input1文件中，请将数据添加到文件中"<

}

else if(x==3)

{

ofstream in1("");

srand(time(NULL));

int n=20000;

int *a=new int[n];

for(int i=0;i

{

a[i]=rand()%91;

in1<

} cout<<"随机数已请生成到input1文件中，请将数据添加到文件中"<

}

cout<<"添加完毕后请输入1"<

int m;

cin>>m;

clock_t start,finish;

start=clock();

for (int i = 1; i <= N; i++)

{

in>>w[i];

}

for (int i = 1; i <= N; i++)

{

in>>p[i];

}

cout<<"已在input文件中读取物品重量和价值。"<

bestp = Knapsack(w, p, c, N, bestx);

for (int i = 1; i <= N; i++)

{

if(i ==1 ) out<<"是否选取：";

out<

if(i != N) out<<",";

else

out<

}

out<<"背包最优价值："<

finish=clock();

out<<"开始时间为:"<

cout<<"结果已生成在文件中"<

system("pause");

return 0;

}

本文发布于:2023-08-01，感谢您对本站的认可！

本文链接:http://torson.com.cn/news/1690822127a437019.html

优先队列式分支限界法求解0-1背包问题

发布评论取消回复

最近发表

相关推荐

标签列表

优先队列式分支限界法求解0-1背包问题

发布评论 取消回复

最近发表

相关推荐

标签列表

发布评论取消回复