C++爱好者 - 网友留言

#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()
{
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<cout<delete []bag;
}


--------------------next---------------------