用分支限界法求解0/1背包问题

来源：百度知道 编辑：UC知道 时间：2024/05/16 12:33:36
分枝限界是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。现要求给出一个具体的0/1背包问题，并用分支限界法求解之。
三、具体要求
（1）给出一个实例
（2）编写算法
（3）编程实现
（4）给出分析

1.问题描述：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。

2.设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

#include

struct good
{
int weight;
int benefit;
int flag;//是否可以装入标记
};

int number=0;//物品数量
int upbound=0;
int curp=0, curw=0;//当前效益值与重量
int maxweight=0;
good *bag=NULL;

void Init_good()
{
bag=new good [number];

for(int i=0; i {
cout<<"请输入第件"<cin>>bag[i].weight;
cout<<"请输入第件"<cin>>bag[i].benefit;
bag[i].flag=0;//初始标志为不装入背包
cout< }

}

int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num {
w=w+bag[num].weight;
p=w+bag[num].benefit;
}

*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}

void LCbag(