01背包问题的解决回溯法.docx
- 文档编号:5020861
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:10
- 大小:16.41KB
01背包问题的解决回溯法.docx
《01背包问题的解决回溯法.docx》由会员分享,可在线阅读,更多相关《01背包问题的解决回溯法.docx(10页珍藏版)》请在冰点文库上搜索。
01背包问题的解决回溯法
前面这块转贴原理及c++代码实现的回溯算法-----带剪枝的递归回溯;最后给出一个不带剪枝的c语言描述的
递归回溯算法且不能给出选择方案,只给出最大价值
回溯法:
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。
它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。
否则,进入该子树,继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。
而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。
这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。
二、算法框架:
1、问题的解空间:
应用回溯法解问题时,首先应明确定义问题的解空间。
问题的解空间应到少包含问题的一个(最优)解。
2、回溯法的基本思想:
确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。
这个开始结点就成为一个活结点,同时也成为当前的扩展结点。
在当前的扩展结点处,搜索向纵深方向移至一个新结点。
这个新结点就成为一个新的活结点,并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。
换句话说,这个结点不再是一个活结点。
此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活结点时为止。
运用回溯法解题通常包含以下三个步骤:
(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
usingnamespacestd;
classKnap
{
friendintKnapsack(intp[],intw[],intc,intn);
public:
voidprint()
{
for(intm=1;m<=n;m++)
{
cout< } cout< }; private: intBound(inti); voidBacktrack(inti); intc;//背包容量 intn;//物品数 int*w;//物品重量数组 int*p;//物品价值数组 intcw;//当前重量 intcp;//当前价值 intbestp;//当前最优值 int*bestx;//当前最优解 int*x;//当前解 }; intKnap: : 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; } voidKnap: : Backtrack(inti) { if(i>n) { if(bestp { for(intj=1;j<=n;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; Backtrack(i+1); } } classObject { friendintKnapsack(intp[],intw[],intc,intn); public: intoperator<=(Objecta)const { return(d>=a.d); } private: intID; floatd; }; intKnapsack(intp[],intw[],intc,intn) { //为Knap: : Backtrack初始化 intW=0; intP=0; inti=1; Object*Q=newObject[n]; for(i=1;i<=n;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;i for(intj=i;j { if(Q[i].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;i<=n;i++) { 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() { int*p; int*w; intc=0; intn=0; inti=0; cout<<"请输入背包个数: "< cin>>n; p=newint[n+1]; w=newint[n+1]; p[0]=0; w[0]=0; cout<<"请输入个背包的价值: "< for(i=1;i<=n;i++) cin>>p[i]; cout<<"请输入个背包的重量: "< for(i=1;i<=n;i++) cin>>w[i]; cout<<"请输入背包容量: "< cin>>c; cout< } /*c*/ #include"stdio.h" #defineN5 intbestp; intcp; intx[N]; voidknap(intc[N],intv[N],intt,intm) { inti; if(t>N-1) { if(bestp } else { if(c[t]<=m) { cp+=v[t]; m-=c[t]; knap(c,v,t+1,m); m+=c[t]; cp-=v[t]; } knap(c,v,t+1,m); } } 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 背包 问题 解决 回溯