蛮力法动态规划法回溯法和分支限界法求解01背包问题.docx
- 文档编号:16067170
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:18
- 大小:19.69KB
蛮力法动态规划法回溯法和分支限界法求解01背包问题.docx
《蛮力法动态规划法回溯法和分支限界法求解01背包问题.docx》由会员分享,可在线阅读,更多相关《蛮力法动态规划法回溯法和分支限界法求解01背包问题.docx(18页珍藏版)》请在冰点文库上搜索。
蛮力法动态规划法回溯法和分支限界法求解01背包问题
蛮力法、动态规划法、回溯法和分支限界法求解01背包问题
一、实验内容:
分别用蛮力法、动态规划法、回溯法和分支限界法求解0/1背包问题。
注:
0/1背包问题:
给定n种物品和一个容量为C的背包,物品i的重量
是wi,其价值为vi,背包问题是如何使选择装入背包内的物品,使得装入背
包中的物品的总价值最大。
其中,每种物品只有全部装入背包或不装入背包
两种选择。
二、所用算法的基本思想及复杂度分析:
1.蛮力法求解0/1背包问题:
1)基本思想:
对于有n种可选物品的0/1背包问题,其解空间由长度为n的0-1
向量组成,可用子集数表示。
在搜索解空间树时,深度优先遍历,搜索每
一个结点,无论是否可能产生最优解,都遍历至叶子结点,记录每次得
到的装入总价值,然后记录遍历过的最大价值。
2)代码:
#includeiostream
#includealgorithm
usingnamespacestd;
#defineN100//最多可能物体数
structgoods//物品结构体
{
intsign;//物品序号
intw;//物品重量
intp;//物品价值
}a[N];
boolm(goodsa,goodsb)
{
return(a.p/a.w)(b.p/b.w);
}
intmax(inta,intb)
{
returnab?
b:
a;
}
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
/*蛮力法求解0/1背包问题*/
intForce(inti)
{
if(in-1){
if(bestPcpcw+a[i].w=C){
for(intk=0;kk++)X[k]=cx[k];//存储最优路径
bestP=cp;
}
returnbestP;
}
cw=cw+a[i].w;
cp=cp+a[i].p;
cx[i]=1;//装入背包
Force(i+1);
cw=cw-a[i].w;
cp=cp-a[i].p;
cx[i]=0;//不装入背包
Force(i+1);
returnbestP;
}
intKnapSack1(intn,goodsa[],intC,intx[])
{
Force(0);
returnbestP;
}
intmain()
{
goodsb[N];
printf("物品种数n:
");
scanf("%d",//输入物品种数
printf("背包容量C:
");
scanf("%d",//输入背包容量
for(inti=0;ii++)//输入物品i的重量w及其价值v
{
printf("物品%d的重量w[%d]及其价值v[%d]:
",i+1,i+1,i+1);
scanf("%d%d",a[i].w,a[i].p);
b[i]=a[i];
}
intsum1=KnapSack1(n,a,C,X);//调用蛮力法求0/1背包问题
printf("蛮力法求解0/1背包问题:
\nX=[");
for(i=0;ii++)
coutX[i]"";//输出所求X[n]矩阵
printf("]装入总价值%d\n",sum1);
bestP=0,cp=0,cw=0;//恢复初始化
}
3)复杂度分析:
蛮力法求解0/1背包问题的时间复杂度为:
T(n)O(2n)。
2.动态规划法求解0/1背包问题:
1)基本思想:
令V(i,j)表示在前i(1in)个物品中能够装入容量为j(1jC)的
背包中的物品的最大值,则可以得到如下动态函数:
V(i,0)V(0,j)0
V(i1,j)(jwi)V(i,j)V(i1,j),V(i1,jwi)vi(jwi)max
按照下述方法来划分阶段:
第一阶段,只装入前1个物品,确定在
各种情况下的背包能够得到的最大价值;第二阶段,只装入前2个物品,
确定在各种情况下的背包能够得到的最大价值;以此类推,直到第n个
阶段。
最后,V(n,C)便是在容量为C的背包中装入n个物品时取得的最
大价值。
2)代码:
#includeiostream
#includealgorithm
usingnamespacestd;
#defineN100//最多可能物体数
structgoods
{//物品结构体
intsign;//物品序号
intw;//物品重量
intp;//物品价值
}a[N];
boolm(goodsa,goodsb)
{
return(a.p/a.w)(b.p/b.w);
}
intmax(inta,intb)
{
returnab?
b:
a;
}
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
intKnapSack2(intn,goodsa[],intC,intx[])
{
intV[N][10*N];for(inti=0;ii++)V[i]=0;for(intj=0;jj++)V[j]=0;for(i=1;ii++)for(j=1;jj++)//初始化第0列//初始化第0行//计算第i行,进行第i次迭代
if(ja[i-1].w)V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p);j=C;//求装入背包的物品for(i=n;ii--){if(V[i][j]V[i-1][j]){x[i-1]=1;j=j-a[i-1].w;x[i-1]=0;}else}returnV[n][C];//返回背包取得的最大价值
}
intmain()
{
goodsb[N];
printf("物品种数n:
");
scanf("%d",//输入物品种数printf("背包容量C:
");scanf("%d",//输入背包容量for(inti=0;ii++)//输入物品i的重量w及其价值v{printf("物品%d的重量w[%d]及其价值v[%d]:
",i+1,i+1,i+1);scanf("%d%d",a[i].w,a[i].p);b[i]=a[i];
}
intsum2=KnapSack2(n,a,C,X);//调用动态规划法求0/1背包问题
printf("动态规划法求解0/1背包问题:
\nX=[");
for(i=0;ii++)coutX[i]"";//输出所求X[n]矩阵printf("]装入总价值%d\n",sum2);for(i=0;ii++){a[i]=b[i];}//恢复a[N]顺序
}
3)复杂度分析:
动态规划法求解0/1背包问题的时间复杂度为:
T(n)O(nC)。
3.回溯法求解0/1背包问题:
1)基本思想:
回溯法:
为了避免生成那些不可能产生最佳解的问题状态,要不断
地利用限界函数(boundingfunction)来处死那些实际上不可能产生所
需解的活结点,以减少问题的计算量。
这种具有限界函数的深度优先生
成法称为回溯法。
对于有n种可选物品的0/1背包问题,其解空间由长度为n的0-1
向量组成,可用子集数表示。
在搜索解空间树时,只要其左儿子结点是一
个可行结点,搜索就进入左子树。
当右子树中有可能包含最优解时就进
入右子树搜索。
2)代码:
#includeiostream
#includealgorithm
usingnamespacestd;
#defineN100//最多可能物体数
structgoods//物品结构体
{
intsign;//物品序号intw;//物品重量
intp;//物品价值
}a[N];
boolm(goodsa,goodsb)
{
return(a.p/a.w)(b.p/b.w);
}
intmax(inta,intb)
{
returnab?
b:
a;
}
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
intBackTrack(inti)
{
if(in-1){if(bestPcp){for(intk=0;kk++)bestP=cp;X[k]=cx[k];//存储最优路径}returnbestP;//进入左子树}if(cw+a[i].w=C){cw=cw+a[i].w;cp=cp+a[i].p;cx[a[i].sign]=1;//装入背包BackTrack(i+1);cw=cw-a[i].w;cp=cp-a[i].p;//回溯,进入右子树
}
cx[a[i].sign]=0;//不装入背包
BackTrack(i+1);
returnbestP;
}
intKnapSack3(intn,goodsa[],intC,intx[])
{
for(inti=0;ii++){x[i]=0;a[i].sign=i;}sort(a,a+n,m);//将各物品按单位重量价值降序排列BackTrack(0);
returnbestP;
}
intmain()
{
goodsb[N];
printf("物品种数n:
");scanf("%d",//输入物品种数printf("背包容量C:
");scanf("%d",//输入背包容量for(inti=0;ii++)//输入物品i的重量w及其价值v{printf("物品%d的重量w[%d]及其价值v[%d]:
",i+1,i+1,i+1);scanf("%d%d",a[i].w,a[i].p);
b[i]=a[i];
}
intsum3=KnapSack3(n,a,C,X);//调用回溯法求0/1背包问题
printf("回溯法求解0/1背包问题:
\nX=[");for(i=0;ii++)coutX[i]"";//输出所求X[n]矩阵printf("]装入总价值%d\n",sum3);for(i=0;ii++){a[i]=b[i];}//恢复a[N]顺序
3)复杂度分析:
最不理想的情况下,回溯法求解0/1背包问题的时间复杂度为:
T(n)O(2n)。
由于其对蛮力法进行优化后的算法,其复杂度一般比蛮力
法要小。
空间复杂度:
有n个物品,即最多递归n层,存储物品信息就是一个
一维数组,即回溯法求解0/1背包问题的空间复杂度为O(n)。
4.分支限界法求解背包问题:
1)基本思想:
分支限界法类似于回溯法,也是在问题的解空间上搜索问题解的算
法。
一般情况下,分支限界法与回溯法的求解目标不同。
回溯法的求解
目标是找出解空间中满足约束条件的所有解,而分支限界法的求解目标
则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某
一目标函数值达到极大或极小的解,即在某种意义下的最优解。
首先,要对输入数据进行预处理,将各物品依其单位重量价值从大
到小进行排列。
在下面描述的优先队列分支限界法中,节点的优先级由已装袋的物
品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。
算法首先检查当前扩展结点的左儿子结点的可行性。
如果该左儿子
结点是可行结点,则将它加入到子集树和活结点优先队列中。
当前扩展
结点的右儿子结点一定是可行结点,仅当右儿子结点满足上界约束时才
将它加入子集树和活结点优先队列。
当扩展到叶节点时为问题的最优值。
2)代码:
#includeiostream
#includealgorithm
usingnamespacestd;
#defineN100//最多可能物体数
structgoods//物品结构体
{
intsign;//物品序号
intw;//物品重量
intp;//物品价值
}a[N];
boolm(goodsa,goodsb)
{
return(a.p/a.w)(b.p/b.w);
}
intmax(inta,intb)
{
returnab?
b:
a;
}
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
struct*****E//状态结构体
{
bools1[N];//当前放入物体
intk;//搜索深度
intb;//价值上界
intw;//物体重量
intp;//物体价值
};
structHEAP//堆元素结构体
{
*****E*p;//结点数据
intb;//所指结点的上界
};
//交换两个堆元素
voidswap(HEAPa,HEAPb)
{
HEAPtemp=a;
a=b;
b=temp;
}
//堆中元素上移
voidmov_up(HEAPH[],inti)
{
booldone=false;
if(i!
=1){
while(!
donei!
=1){
if(H[i].bH[i/2].b){
swap(H[i],H[i/2]);
}else{
done=true;
}
i=i/2;
}
}
}
//堆中元素下移
voidmov_down(HEAPH[],intn,inti)
{
booldone=false;
if((2*i)=n){
while(!
done((i=2*i)=n)){
if(i+1=nH[i+1].bH[i].b){
i++;
}
if(H[i/2].bH[i].b){
swap(H[i/2],H[i]);
}else{
done=true;
}
}
}
}
//往堆中插入结点
voidinsert(HEAPH[],HEAPx,intn)
{
n++;
H[n]=x;
mov_up(H,n);
}
//删除堆中结点
voiddel(HEAPH[],intn,inti)
{
HEAPx,y;
x=H[i];y=H[n];
n--;
if(i=n){
H[i]=y;
if(y.b=x.b){
mov_up(H,i);
}else{
mov_down(H,n,i);
}
}
}
//获得堆顶元素并删除
HEAPdel_top(HEAPH[],intn)
{
HEAPx=H;
del(H,n,1);
returnx;
}
//计算分支节点的上界
voidbound(*****E*node,intM,goodsa[],intn)
{
inti=node-
floatw=node-
floatp=node-
if(node-wM){//物体重量超过背包载重量
node-b=0;//上界置为0
}else{
while((w+a[i].w=M)(in)){
w+=a[i].w;//计算背包已装入载重
p+=a[i++].p;//计算背包已装入价值
}
if(in){
node-b=p+(M-w)*a[i].p/a[i].w;
}else{
node-b=p;
}
}
}
//用分支限界法实现0/1背包问题
intKnapSack4(intn,goodsa[],intC,intX[])
{
inti,k=0;//堆中元素个数的计数器初始化为0
intv;
*****E*xnode,*ynode,*znode;
HEAPx,y,z,*heap;
heap=newHEAP[n*n];//分配堆的存储空间
for(i=0;ii++){
a[i].sign=i;//记录物体的初始编号
}
sort(a,a+n,m);//对物体按照价值重量比排序
xnode=new*****E;//建立父亲结点
for(i=0;ii++){//初始化结点
xnode-s1[i]=false;
}
xnode-k=xnode-w=xnode-p=0;
while(xnode-kn){
ynode=new*****E;//建立结点y
*ynode=*xnode;//结点x的数据复制到结点y
ynode-s1[ynode-k]=true;//装入第k个物体
ynode-w+=a[ynode-k].w;//背包中物体重量累计
ynode-p+=a[ynode-k].p;//背包中物体价值累计
ynode-k++;//搜索深度++
bound(ynode,C,a,n);//计算结点y的上界
y.b=ynode-
y.p=ynode;
insert(heap,y,k);//结点y按上界的值插入堆中
znode=new*****E;//建立结点z
*znode=*xnode;//结点x的数据复制到结点z
znode-//搜索深度++
bound(znode,C,a,n);//计算节点z的上界
z.b=znode-
z.p=znode;
insert(heap,z,k);//结点z按上界的值插入堆中
deletexnode;
x=del_top(heap,k);//获得堆顶元素作为新的父亲结点
xnode=x.p;
}
v=xnode-
for(i=0;ii++){//取装入背包中物体在排序前的序号
if(xnode-s1[i]){
X[a[i].sign]=1;
}else{
X[a[i].sign]=0;
}
}
deletexnode;
deleteheap;
returnv;//返回背包中物体的价值
}
/*测试以上算法的主函数*/
intmain()
{
goodsb[N];
printf("物品种数n:
");
scanf("%d",//输入物品种数
printf("背包容量C:
");
scanf("%d",//输入背包容量
for(inti=0;ii++)//输入物品i的重量w及其价值v
{
printf("物品%d的重量w[%d]及其价值v[%d]:
",i+1,i+1,i+1);
scanf("%d%d",a[i].w,a[i].p);
b[i]=a[i];
}
intsum4=KnapSack4(n,a,C,X);//调用分支限界法求0/1背包问题
printf("分支限界法求解0/1背包问题:
\nX=[");
for(i=0;ii++)
coutX[i]"";//输出所求X[n]矩阵
printf("]装入总价值%d\n",sum4);
return0;
}
3)复杂度分析:
分支限界法求解0/1背包问题的时间复杂度为:
T(n)O(2n)。
相同的数据,求相同同的问题,用不同的方法,得到的结果,所得结果正式所求问题的最优解,所编程序是正确的。
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训:
1.本实验中4种算法要用同一个主函数调用,由于背包容量、物品、解向量
等变量都是以全局变量定义的,每次调用一种算法之前,必须要看这些重要的变
量值是否因上一个算法的调用而发生了改变,如发生改变,则需将其改回原值,使得各种算法之间互不影响。
2.在本实验中,各种算法因申请存储空间等原因,运行时间的排序不可能与其时间复杂度的一致,甚至可能会有很大差别,又不可能输入大量数据进行各种算法的测试,所以没有求各算法的运行时间并进行比较。
即各算法的运行时间受较多因素影响,较小数据量时与算法时间复杂度无相关性,比较是没有意义的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 蛮力法 动态 规划 回溯 分支 限界 求解 01 背包 问题