de*nnoder(node*parent1,intisin1,doubleub1);生成一个新的结点voidaddnode(node*node1);//将结点添加到队列中node*nextnode();//取下一个结点voidfenzjx();//分支界限法的主要实现函数voidoutput();//用于输出物品的选择情况及最优解4.3输入/输出设计本程序通过键盘进行输入、屏幕进行输出。4.4符号名说明符号说明c背包的容量n物品的个数pro存放物品信息avg物品的单位价值量opv背包容量最优解popv指向最优解的指针level节点的层cw当前背包装载量cv当前背包价值ub节点的上界值isin记录当前结点物品是否放入背包flag物品原来位置算法描述算法的伪代码描述如下:输入:背包的容量c,物品的个数n,n个物品的信息pro[n]输出:装入背包的物品标号和背包获得的最大价值1.对输入的物品按照单位价值量递减的顺序进行排序2.初始化问题最优解opv=0,初始化第0层结点,计算上界值ub=Upb(0,0,0);并设置该结点设为优先级队列的根结点3.循环直到优先级队列为空3.1如果取出当前结点位于第n-1层,则其子结点已是叶子结点,判断子结点取值情况,若得到的解大于当前问题得到的最优解opv,则重置问题的最优解opv3.2如果取出当前结点层level<n-1对结点i的每个孩子结点x执行下列操作:3.2.1如果结点x可能产生的最优解ub<opv,则丢弃该结点;3.2.2否则估算该节点x的目标函数值ub,将结点加入队列;4.将该结点对应的最优值输出,回溯求得最优解的各个分量三、源程序及注释:?1、蛮力法#include<iostream>#include<math.h>usingnamespacestd;//物品typedefstructobj{?intw;?intv;};//生成子集
全文预览
