01背包问题的解决回溯法Word格式文档下载.docx
- 文档编号:7103366
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:10
- 大小:16.41KB
01背包问题的解决回溯法Word格式文档下载.docx
《01背包问题的解决回溯法Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《01背包问题的解决回溯法Word格式文档下载.docx(10页珍藏版)》请在冰点文库上搜索。
如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。
换句话说,这个结点不再是一个活结点。
此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤:
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;
3、递归回溯:
由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯法。
【概要设计】
0—1背包问题是一个子集选取问题,适合于用子集树表示0—1背包问题的解空间。
在搜索解空间树是,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。
否则将右子树剪去。
intc;
//背包容量
intn;
//物品数
int*w;
//物品重量数组
int*p;
//物品价值数组
intcw;
//当前重量
intcp;
//当前价值
intbestp;
//当前最优值
int*bestx;
//当前最优解
int*x;
//当前解
intKnap:
:
Bound(inti)//计算上界
voidKnap:
Backtrack(inti)//回溯
intKnapsack(intp[],intw[],intc,intn)//为Knap:
Backtrack初始化
【详细设计】
#include<
iostream>
usingnamespacestd;
classKnap
{
friendintKnapsack(intp[],intw[],intc,intn);
public:
voidprint()
for(intm=1;
m<
=n;
m++)
cout<
<
bestx[m]<
"
"
;
}
endl;
};
private:
intBound(inti);
voidBacktrack(inti);
Bound(inti)
//计算上界
intcleft=c-cw;
//剩余容量
intb=cp;
//以物品单位重量价值递减序装入物品
while(i<
=n&
&
w[i]<
=cleft)
cleft-=w[i];
b+=p[i];
i++;
//装满背包
if(i<
=n)
b+=p[i]/w[i]*cleft;
returnb;
Backtrack(inti)
if(i>
n)
if(bestp<
cp)
for(intj=1;
j<
j++)
bestx[j]=x[j];
bestp=cp;
return;
if(cw+w[i]<
=c)//搜索左子树
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
if(Bound(i+1)>
bestp)//搜索右子树
x[i]=0;
classObject
friendintKnapsack(intp[],intw[],intc,intn);
intoperator<
=(Objecta)const
return(d>
=a.d);
intID;
floatd;
intKnapsack(intp[],intw[],intc,intn)
//为Knap:
intW=0;
intP=0;
inti=1;
Object*Q=newObject[n];
for(i=1;
i<
i++)
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;
//装入所有物品
//依物品单位重量排序
floatf;
for(i=0;
n;
for(intj=i;
if(Q[i].d<
Q[j].d)
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
KnapK;
K.p=newint[n+1];
K.w=newint[n+1];
K.x=newint[n+1];
K.bestx=newint[n+1];
K.x[0]=0;
K.bestx[0]=0;
for(i=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;
K.bestp=0;
//回溯搜索
K.Backtrack
(1);
K.print();
delete[]Q;
delete[]K.w;
delete[]K.p;
returnK.bestp;
voidmain()
intc=0;
intn=0;
inti=0;
请输入背包个数:
cin>
>
p=newint[n+1];
w=newint[n+1];
p[0]=0;
w[0]=0;
请输入个背包的价值:
p[i];
请输入个背包的重量:
w[i];
请输入背包容量:
c;
Knapsack(p,w,c,n)<
/*c*/
#include"
stdio.h"
#defineN5
intx[N];
voidknap(intc[N],intv[N],intt,intm)
inti;
if(t>
N-1)
cp)bestp=cp;
else
if(c[t]<
=m)
cp+=v[t];
m-=c[t];
knap(c,v,t+1,m);
m+=c[t];
cp-=v[t];
main()
intc[]={2,2,6,5,4},v[]={6,3,5,4,6};
intm=10;
knap(c,v,0,m);
printf("
%d\n"
bestp);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 01 背包 问题 解决 回溯