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

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<<"请输入第件">bag[i].weight;
cout<<"请输入第件">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()
{
int bound_u=0, bound_c=0;//当前结点的c限界和u限界

for(int i=0; i {
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍历左子树
upbound=bound_u;//更改已有u限界,不更改标志

if( getbound(i, &bound_u)>bound_c )//遍历右子树
//若装入，判断右子树的c限界是否大于左子树根的c限界，是则装入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//从已有重量和效益加上新物品
bag[i].flag=1;//标记为装入
}
}

}

void Display()
{

cout<<"可以放入背包的物品的编号为：";
for(int i=0; iif(bag[i].flag>0)

cout<
｝

参考：
http://cache.baidu.com/c?word=%B7%D6%D6%A7%3B%CF%DE%BD%E7%3B%B7%A8%3B%C7%F3%BD%E2%3B0%2C1%3B%B1%B3%B0%FC%3B%CE%CA%CC%E2&url=http%3A//www%2Edaxiongonline%2Ecom/dvbbs/dispbbs%2Easp%3FboardID%3D31%26ID%3D1016&b=10&a=0&user=baidu