采用优先队列式分枝限界法求解0/1背包问 题.pdf
需积分: 6 84 浏览量
2020-05-25
17:26:47
上传
评论 3
收藏 125KB PDF 举报
//采用优先队列式分枝限界法求解0/1背包问
题
#include <stdio.h>
#include <queue>
using namespace std;
#define MAXN 20
//最多可能物品数
//问题表示
int n=3,W=30;
int w[]={0,16,15,15};
//重量，下标0不用
int v[]={0,45,25,25};
//价值，下标0不用
//求解结果表示
int maxv=-9999;
//存放最大价值,初始为最
小值
int bestx[MAXN];
//存放最优解,全局变量
int total=1;
//解空间中结点数累计,全
局变量
struct NodeType
//队列中的结点类型
{ int no;
//结点编号
int i;
//当前结点在搜索
空间中的层次
int w;
//当前结点的总重
量
int v;
//当前结点的总价
值
int x[MAXN];
//当前结点包含的解向量
double ub;
//上界
};
void bound(NodeType &e)
//计算分枝结点e的上界
{
int i=e.i+1;
int sumw=e.w;
double sumv=e.v;
while ((sumw+w[i]<=W) && i<=n)
{ sumw+=w[i];
//计算背包已装入载重
sumv+=v[i];
//计算背包已装入价值
i++;
}
if (i<=n)
e.ub=sumv+(W-sumw)*v[i]/
w[i];
else
e.ub=sumv;
}
void EnQueue(NodeType e,queue<NodeType>
&qu) //结点e进队qu
{
if (e.i==n)
//到达叶子结点
{
if (e.v>maxv)
//找到更大价值的解
{
maxv=e.v;
for (int
j=1;j<=n;j++)
bestx[j]=e.x[j];
}
}
else qu.push(e);
//非叶子结点进队
}
void bfs()
//求0/1背包的最
优解
{
int j;
NodeType e,e1,e2;
//定义3个结点
queue<NodeType> qu;
//定义一个队列
e.i=0;
//根结点置初值，
其层次计为0
e.w=0; e.v=0;
e.no=total++; //e.no=1,total=3
for (j=1;j<=n;j++)
e.x[j]=0;
//x[1]=0;x[2]=0;x[3]=0
bound(e);
//求根结点的上界
qu.push(e);
//根结点进队
1.while (!qu.empty())
//队不空循环
{
e=qu.front(); qu.pop();
//出队结点e//出队结点1
if (e.w+w[e.i+1]<=W)
//剪枝：检查左孩子结点
{
e1.no=total++;
//e1.no=2;total=3
e1.i=e.i+1;
//建立左孩子结点
=1
e1.w=e.w+w[e1.i];//16
e1.v=e.v+v[e1.i];//45
for (j=1;j<=n;j++)
//复制解向量
e1.x[j]=e.x[j];
e1.x[e1.i]=1;//x[1]=1;x[2]=0;x[3]=0
bound(e1);
//求左孩子结点的
上界ub=68
EnQueue(e1,qu);
//左孩子结点2进队操作
}
e2.no=total++;//e2.no=3;total=4
//建立右孩子结点
e2.i=e.i+1;
e2.w=e.w;
e2.v=e.v;//w=0,v=0
for (j=1;j<=n;j++)
//复制解向量
e2.x[j]=e.x[j];
e2.x[e2.i]=0;//x[1]=0;x[2]=0;x[3]=0
bound(e2);
//求右孩子结点的
上界ub=50
if (e2.ub>maxv)//结点3进队
//若右孩子结点可
行,则进队,否则被剪枝
EnQueue(e2,qu);
}
}
void main()
{
bfs();
//调用队列式分枝限界法求0/1背包
问题
printf("分枝限界法求解0/1背包问
题: X=["); //输出最优解
for(int i=1;i<=n;i++)
printf("%2d",bestx[i]);
//输出所求X[n]数组
printf("]，装入总价值为%d\
n",maxv);
}
2.while (!qu.empty())
//
队不空循环
{
e=qu.front();
qu.pop(); //出队结点
2
if
(e.w+w[e.i+1]<=W)
//否，左剪枝
{}//16+w[2]=31>30
e2.no=total++;
//e2.no=4; total=5
e2.i=2;
//建立右孩
子结点
e2.w=16;
e2.v=45;
for (j=1;j<=n;j++)
//复制解向量
e2.x[j]=e.x[j];
e2.x[e2.i]=0;//x[1]=1
;x[2]=0;x[3]=0
bound(e2);
//
求右孩子结点4的上界68
if(e2.ub>maxv //
右孩子结点4进队
EnQueue(e2,qu);
}
3.while (!qu.empty())
//
队不空循环
{
e=qu.front();
qu.pop(); //出队结点
4
if
(e.w+w[e.i+1]<=W)
//否，左剪枝
{}//16+w[2]=31>30
e2.no=total++;
//e2.no=5; total=6
e2.i=3;
//建立右孩
子结点
e2.w=16;
e2.v=45;
for (j=1;j<=n;j++)
//复制解向量
e2.x[j]=e.x[j];
e2.x[e2.i]=0;//x[1]=1
;x[2]=0;x[3]=0
bound(e2);
//
求右孩子结点4的上界45
if(e2.ub>maxv //
右孩子结点5看能否进队
EnQueue(e2,qu);
}5为叶子不能进对
EnQueue(e2,quEue<NodeTyp
e>&qu)
{
if(e2.i==3) //到达叶子结
点；
{
if（e2.v>maxv）//45>-
9999
{
maxv=e2.v;//maxv=45
for(int j=1;j<=3;j++)
Best[j]=e.x[j];}
//best[1]=1;best[2]=0;best[3]=
0
}};
找到一个可行解
4.while (!qu.empty())
//队不空循环
{
e=qu.front(); qu.pop();
//出队结点3
if (e.w+w[e.i+1]<=W)
//剪枝：检查左孩子结
点
{
e1.no=total++;
//e1.no=6;total=7
e1.i=e.i+1=2;
//建
立左孩子结点
e1.w=e.w+w[e1.i]=15;
e1.v=e.v+v[e1.i]=25;
for (j=1;j<=n;j++) //复制解向量
e1.x[j]=e.x[j];
e1.x[e1.i]=1;//x[1]=0;x[2]=1;x[3]
=0
bound(e1);
//求
左孩子结点的上界50
EnQueue(e1,qu);
//左孩子结点6进队操作
}
e2.no=total++;//e2.no=7;total=8
e2.i=e.i+1=2;//建立右孩子结点
e2.w=e.w=0;
e2.v=e.v=0;
for (j=1;j<=n;j++)
//复制解向量
e2.x[j]=e.x[j];
e2.x[e2.i]=0;//x[1]=0;x[2]=0;x[3]
=0
bound(e2);
//求
右孩子结点的上界25
if (e2.ub>maxv)
//否右孩子节
点ub小于45被剪枝}//但是占用了编号7
5.while (!qu.empty())
//队不空循环
{
e=qu.front();
qu.pop(); //出队结点6
if
(e.w+w[e.i+1]<=W)
//剪枝：检查左孩子结点
{
e1.no=total++;
//e1.no=8;total=9
e1.i=e.i+1=3;
//建立左孩子结点
e1.w=e.w+w[e1.i]=30;
e1.v=e.v+v[e1.i]=50;
for (j=1;j<=n;j++) //复制解
向量
e1.x[j]=e.x[j];
e1.x[e1.i]=1;//x[1]=0;x[2]=1;
x[3]=1
bound(e1);
//求左孩子结点的上界50
EnQueue(e1,qu);
//左孩子结点6进队操作
}
e2.no=total++;//e2.no=9;total=10
e2.i=e.i+1=3;//建立右孩子结点
e2.w=e.w=15;
e2.v=e.v=25;
for (j=1;j<=n;j++)
//复制解向量
e2.x[j]=e.x[j];
e2.x[e2.i]=0;//x[1]=0;x[2]=1;
x[3]=0
bound(e2);
//求右孩子结点的上界25
if (e2.ub>maxv)
//否右孩
子节点ub小于50被剪枝}//但占用一
个编号9
EnQueue(e2,quEue<NodeType>&qu)
{
if(e2.i==3) //到达叶子结点；
{
if（e2.v>maxv）//50>45
{
maxv=e2.v;//maxv=50
for(int j=1;j<=3;j++)
Best[j]=e.x[j];}
//best[1]=0;best[2]=1;best[3]=1
}};
EnQueue(e2,quEue<NodeType>&qu)
{
if(e2.i==3) //到达叶子结点；
{
if（e2.v>maxv）//50>45
{
maxv=e2.v;//maxv=50
for(int j=1;j<=3;j++)
Best[j]=e.x[j];}
//best[1]=;best[2]=0;best[3]=1
}};
资源评论
