0/1背包问题的分支限界算法
提问于2008-04-24 10:30:27 解决时间:2008-04-30 14:26:23
利用优先级分支限界法设计0/1背包问题的算法，掌握分支限界法的基本思想和算法设计的基本步骤，注意其中结点优先级的确定方法，要有利于找到最优解的启发信息。
要求：设计0/1背包问题的分支限界算法，利用c语言（c++语言）实现算法，给出程序的正确运行结果。
注意：
1. 把物品按照单位体积的价值降序排列；
2. 构造优先级分支限界法的状态空间树，共n层，第i层每个节点的两个分支分别代表第i个物品的取和不取；
3. 节点上需要保存的值有：S代表已装入背包的物品的总体积，V代表已装入背包的物品的总价值，u代表当前节点的上界，计算公式如下：
u=V+（C-S）（vi+1/si+1）
其中C是背包的总容积，vi+1代表第i+1个物品的价值，si+1代表第i+1个物品的体积。
4. 选择适当的数据结构（如最大堆，或者基本的线性数组）实现算法，输出最后结果。
设计思想与分析：对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。
#include <iostream.h>
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<number; i++)
{
cout<<"请输入第件"<<i+1<<"物品的重量:";
cin>>bag.weight;
cout<<"请输入第件"<<i+1<<"物品的效益:";
cin>>bag.benefit;
bag.flag=0;//初始标志为不装入背包
cout<<endl;
}
}
int getbound(int num, int *bound_u)//返回本结点的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; 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<number; 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.benefit;
curw=curw+bag.weight;//从已有重量和效益加上新物品
bag.flag=1;//标记为装入
}
}
}
void Display()
{
cout<<"可以放入背包的物品的编号为：";
for(int i=0; i<number; i++)
if(bag.flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}
类！！
|
