第五组分支限界法(0-1背包问题)

实训一0-1背包问题的分支限界法与实现任务分配成员1张藤成绩综合分数成员2 金洲成绩一、 设计目的1） 掌握0-1背包问题的分支限界法；2） 进一步掌握分支限界法的基本思想和算法设计方法；二、 设计内容1 任务描述1） 算法简介分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支限界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。分支限界法的搜索策略是，在扩展结点处，先生成其所有的儿子结点(分支)，然后再从当前的活结点表中选择下一扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)，并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。这种方式称为分支限界法。人们已经用分支限界法解决了大量离散最优化的问题。2） 0-1背包问题简介给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。3） 设计任务简介对于分支限界类似的问题。首先，要能理解该问题运用到的分支限界的概念；其次，根据分支限界相关的基本思想，找出相应的数学公式；最后，进行程序的设计和编写。利用分支限界的基本思想和计算步骤，有助于我们解决生活中遇到的各种数学问题。4） 问题分析在解0-1背包问题的优先队列式分支限界法中，活结点优先队列中结点元素N的优先级由该结点的上界函数Bound计算出的值uprofit给出。子集树中以结点N为根的子树中任一结点的价值不超过N.profit。可用一个最大堆来实现活结点优先队列。堆中元素类型为HeapNode，其私有成员有uprofit,profit,weight和level。对于任意活结点N，N.weight是结点N所相应的重量；N.profit是N所相应的价值；N.uprofit是结点N的价值上界，最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。0-1背包问题的表示方案2 递推过程的抽象描述本设计采用前向或后向递推公式。用自然语言、伪程序设计语言或流程图等形式针对0-1背包问题的求解（抽象地）描述递推过程3 主要数据类型与变量float weight;/物品重量 float value;/物品价值 intceng;/ struct QNode *parent;/子结点 bool leftChild;/左儿子结点4 算法或程序模块void maxLoading(float w,float v,int c)float wt=0;float vt=0;int i=1; /当前的扩展结点所在的层float ew=0; /扩展节点所相应的当前载重量float ev=0; /扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /空标志进队列while (!QueueEmpty(sq)wt=ew+wi;vt=ev+vi;if (wt bestv)bestv=vt;EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列EnQueue1(ew,ev,i,e,false); /右儿子总是可行；e=DeQueue(sq); / 取下一扩展结点if (e = NULL)if (QueueEmpty(sq) break;EnQueue(sq,NULL); / 同层结点尾部标志e=DeQueue(sq); / 取下一扩展结点i+;ew=e-weight; /更新当前扩展结点的值ev=e-value;printf(最优价值为：%.0fnn,bestv);printf(最优取法为：n);for( int j=n-1;j0;j-) /构造最优解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(int k=1;k=n;k+)if(bestxk=1)printf(n物品%d:重量：%.0f，价值：%.0fnn,k,wk,vk);三、 测试1 方案描述测试方案、测试模块、测试数据实例（文字数据、图或表等形式）2 结果四、 总结与讨论通过构造函数，利用回溯思想编写代码，利用回溯的基本思想和计算步骤，有助于我们解决生活中遇到的各种数学问题。附：程序模块的源代码#include #include#define MaxSize 100 /最多结点数typedef struct QNodefloat weight; float value; intceng; struct QNode *parent; bool leftChild;QNode,*qnode; /存放每个结点typedef structqnode QMaxSize; int front,rear;SqQueue; /存放结点的队列SqQueue sq;float bestv=0; /最优解int n=0; /实际物品数float wMaxSize; /物品的重量float vMaxSize;/物品的价值int bestxMaxSize; / 存放最优解qnode bestE;void InitQueue(SqQueue &sq ) /队列初始化sq.front=1;sq.rear=1;bool QueueEmpty(SqQueue sq) /队列是否为空if(sq.front=sq.rear)return true;elsereturn false;void EnQueue(SqQueue &sq,qnode b)/入队if(sq.front=(sq.rear+1)%MaxSize)printf(队列已满!);return ;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue &sq)/出队qnode e;if(sq.front=sq.rear)printf(队列已空!);return 0;e=sq.Qsq.front;sq.front=(sq.front+1)%MaxSize;return e;void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if (i=n) /可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode); /非叶子结点b-weight=wt;b-value=vt;b-ceng=i;b-parent=parent;b-leftChild=leftchild;EnQueue(sq,b);void maxLoading(float w,float v,int c)float wt=0;float vt=0;int i=1; /当前的扩展结点所在的层float ew=0; /扩展节点所相应的当前载重量float ev=0; /扩展结点所相应的价值qnode e=NULL;qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /空标志进队列while (!QueueEmpty(sq)wt=ew+wi;vt=ev+vi;if (wt bestv)bestv=vt;EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列EnQueue1(ew,ev,i,e,false); /右儿子总是可行；e=DeQueue(sq); / 取下一扩展结点if (e = NULL)if (QueueEmpty(sq) break;EnQueue(sq,NULL); / 同层结点尾部标志e=DeQueue(sq); / 取下一扩展结点i+;ew=e-weight; /更新当前扩展结点的值ev=e-value;printf(最优价值为：%.0fnn,bestv);printf(最优取法为：n);for( int j=n-1;j0;j-) /构造最优解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(int k=1;k=n;k+)if(bestxk=1)printf(n物品%d:重量：%.0f，价值：%.0fnn,k,wk,vk);void main()int c;float ewvMaxSize;printf( / 0-1背包问题分枝限界法 /nn);printf(请输入物品的数量：n);scanf(%d,&n);prin