01背包分支要点Word格式.docx
- 文档编号:7846472
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:13
- 大小:31.98KB
01背包分支要点Word格式.docx
《01背包分支要点Word格式.docx》由会员分享,可在线阅读,更多相关《01背包分支要点Word格式.docx(13页珍藏版)》请在冰点文库上搜索。
{C}—>
{F,G}—>
{G,L,M}—>
{G,M}—>
{G}—>
{N,O}—>
{O}—>
{}
//0-1背包问题分支限界法求解
#include"
stdafx.h"
MaxHeap.h"
#include<
iostream>
usingnamespacestd;
classObject
{
template<
classTypew,classTypep>
friendTypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[]);
public:
intoperator<
=(Objecta)const
{
returnd>
=a.d;
}
private:
intID;
floatd;
//单位重量价值
};
template<
classKnap;
classbbnode
friendKnap<
int,int>
;
bbnode*parent;
//指向父节点的指针
boolLChild;
//左儿子节点标识
classHeapNode
Typew,Typep>
operatorTypep()const
returnuprofit;
Typepuprofit,//节点的价值上界
profit;
//节点所相应的价值
Typewweight;
//节点所相应的重量
intlevel;
//活节点在子集树中所处的层序号
bbnode*ptr;
//指向活节点在子集中相应节点的指针
classKnap
TypepMaxKnapsack();
MaxHeap<
HeapNode<
Typep,Typew>
>
*H;
TypepBound(inti);
voidAddLiveNode(Typepup,Typepcp,Typewcw,boolch,intlev);
bbnode*E;
//指向扩展节点的指针
Typewc;
//背包容量
intn;
//物品数
Typew*w;
//物品重量数组
Typep*p;
//物品价值数组
Typewcw;
//当前重量
Typepcp;
//当前价值
int*bestx;
//最优解
template<
classType>
inlinevoidSwap(Type&
a,Type&
b);
voidBubbleSort(Typea[],intn);
intmain()
intn=3;
//物品数
intc=30;
//背包容量
intp[]={0,45,25,25};
//物品价值下标从1开始
intw[]={0,16,15,15};
//物品重量下标从1开始
intbestx[4];
//最优解
cout<
<
"
背包容量为:
c<
endl;
物品重量和价值分别为:
for(inti=1;
i<
=n;
i++)
("
w[i]<
"
p[i]<
)"
背包能装下的最大价值为:
Knapsack(p,w,c,n,bestx)<
此背包问题最优解为:
bestx[i]<
"
return0;
}
TypepKnap<
:
Bound(inti)//计算节点所相应价值的上界
Typewcleft=c-cw;
//剩余容量高
Typepb=cp;
//价值上界
//以物品单位重量价值递减序装填剩余容量
while(i<
=n&
&
w[i]<
=cleft)
cleft-=w[i];
b+=p[i];
i++;
//装填剩余容量装满背包
if(i<
=n)
b+=p[i]/w[i]*cleft;
returnb;
//将一个活节点插入到子集树和优先队列中
voidKnap<
AddLiveNode(Typepup,Typepcp,Typewcw,boolch,intlev)
bbnode*b=newbbnode;
b->
parent=E;
LChild=ch;
HeapNode<
N;
N.uprofit=up;
N.profit=cp;
N.weight=cw;
N.level=lev;
N.ptr=b;
H->
Insert(N);
//优先队列式分支限界法,返回最大价值,bestx返回最优解
MaxKnapsack()
H=newMaxHeap<
(1000);
//为bestx分配存储空间
bestx=newint[n+1];
//初始化
inti=1;
E=0;
cw=cp=0;
Typepbestp=0;
//当前最优值
Typepup=Bound
(1);
//搜索子集空间树
while(i!
=n+1)
//检查当前扩展节点的左儿子节点
Typewwt=cw+w[i];
if(wt<
=c)//左儿子节点为可行节点
if(cp+p[i]>
bestp)
bestp=cp+p[i];
AddLiveNode(up,cp+p[i],cw+w[i],true,i+1);
up=Bound(i+1);
//检查当前扩展节点的右儿子节点
if(up>
=bestp)//右子树可能含有最优解
AddLiveNode(up,cp,cw,false,i+1);
//取下一扩展节点
DeleteMax(N);
E=N.ptr;
cw=N.weight;
cp=N.profit;
up=N.uprofit;
i=N.level;
//构造当前最优解
for(intj=n;
j>
0;
j--)
bestx[j]=E->
LChild;
E=E->
parent;
returncp;
//返回最大价值,bestx返回最优解
TypepKnapsack(Typepp[],Typeww[],Typewc,intn,intbestx[])
TypewW=0;
//装包物品重量
TypepP=0;
//装包物品价值
//定义依单位重量价值排序的物品数组
Object*Q=newObject[n];
//单位重量价值数组
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
if(W<
=c)
returnP;
//所有物品装包
//依单位价值重量排序
BubbleSort(Q,n);
//创建类Knap的数据成员
Knap<
K;
K.p=newTypep[n+1];
K.w=newTypew[n+1];
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
//调用MaxKnapsack求问题的最优解
Typepbestp=K.MaxKnapsack();
for(intj=1;
j<
j++)
bestx[Q[j-1].ID]=K.bestx[j];
deleteQ;
delete[]K.w;
delete[]K.p;
delete[]K.bestx;
returnbestp;
voidBubbleSort(Typea[],intn)
//记录一次遍历中是否有元素的交换
boolexchange;
for(inti=0;
n-1;
i++)
exchange=false;
for(intj=i+1;
=n-1;
if(a[j]<
=a[j-1])
Swap(a[j],a[j-1]);
exchange=true;
//如果这次遍历没有元素的交换,那么排序结束
if(false==exchange)
break;
b)
Typetemp=a;
a=b;
b=temp;
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 01 背包 分支 要点