蛮力法动态规划法回溯法和分支限界法求解01背包问题Word格式.docx
《蛮力法动态规划法回溯法和分支限界法求解01背包问题Word格式.docx》由会员分享，可在线阅读，更多相关《蛮力法动态规划法回溯法和分支限界法求解01背包问题Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
intForce（inti）
if（i>
n-1）{
if（bestP<
cp&
&
cw+a[i].w<
=C）{
for（intk=0;
k<
n;
k++）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;
//不装入背包
returnbestP;
intKnapSack1（intn,goodsa[],intC,intx[]）
Force（0）;
intmain（）
goodsb[N];
printf（"
物品种数n:
"
）;
scanf（"
%d"
&
n）;
//输入物品种数
背包容量C:
C）;
//输入背包容量
for（inti=0;
i<
i++）//输入物品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背包问题
蛮力法求解0/1背包问题:
\nX=["
for（i=0;
i++）
cout<
<
X[i]<
"
;
//输出所求X[n]矩阵
]装入总价值%d\n"
sum1）;
bestP=0,cp=0,cw=0;
//恢复初始化
3）复杂度分析：
蛮力法求解0/1背包问题的时间复杂度为：
。
2.动态规划法求解0/1背包问题：
令
表示在前
个物品中能够装入容量为
的背包中的物品的最大值，则可以得到如下动态函数：
按照下述方法来划分阶段：
第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；
第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；
以此类推，直到第
个阶段。
最后，
便是在容量为
的背包中装入
个物品时取得的最大价值。
2）代码：
#include<
usingnamespacestd;
#defineN100//最多可能物体数
structgoods//物品结构体
intsign;
intw;
intp;
}a[N];
boolm（goodsa,goodsb）
return（a.p/a.w）>
intmax（inta,intb）
returna<
intn,C,bestP=0,cp=0,cw=0;
intX[N],cx[N];
intKnapSack2（intn,goodsa[],intC,intx[]）
intV[N][10*N];
for（inti=0;
=n;
i++）//初始化第0列
V[i][0]=0;
for（intj=0;
j<
=C;
j++）//初始化第0行
V[0][j]=0;
for（i=1;
i++）//计算第i行，进行第i次迭代
for（j=1;
j++）
if（j<
a[i-1].w）
V[i][j]=V[i-1][j];
else
V[i][j]=max（V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p）;
j=C;
//求装入背包的物品
for（i=n;
i>
0;
i--）
{
if（V[i][j]>
V[i-1][j]）{
x[i-1]=1;
j=j-a[i-1].w;
}
elsex[i-1]=0;
}
returnV[n][C];
//返回背包取得的最大价值
intmain（）
goodsb[N];
for（inti=0;
{
printf（"
scanf（"
b[i]=a[i];
intsum2=KnapSack2（n,a,C,X）;
//调用动态规划法求0/1背包问题
动态规划法求解0/1背包问题:
for（i=0;
cout<
sum2）;
for（i=0;
a[i]=b[i];
}//恢复a[N]顺序
3）复杂度分析:
动态规划法求解0/1背包问题的时间复杂度为：
3.回溯法求解0/1背包问题：
回溯法：
为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数（boundingfunction）来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。
这种具有限界函数的深度优先生成法称为回溯法。
在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入左子树。
当右子树中有可能包含最优解时就进入右子树搜索。
2）代码:
intBackTrack（inti）
if（i>
if（bestP<
cp）{
bestP=cp;
}
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）;
intKnapSack3（intn,goodsa[],intC,intx[]）
x[i]=0;
a[i].sign=i;
sort（a,a+n,m）;
//将各物品按单位重量价值降序排列
BackTrack（0）;
intsum3=KnapSack3（n,a,C,X）;
//调用回溯法求0/1背包问题
回溯法求解0/1背包问题:
sum3）;
}//恢复a[N]顺序
最不理想的情况下，回溯法求解0/1背包问题的时间复杂度为：
由于其对蛮力法进行优化后的算法，其复杂度一般比蛮力法要小。
空间复杂度：
有
个物品，即最多递归
层，存储物品信息就是一个一维数组，即回溯法求解0/1背包问题的空间复杂度为
4.分支限界法求解背包问题：
分支限界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。
一般情况下，分支限界法与回溯法的求解目标不同。
回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。
在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。
算法首先检查当前扩展结点的左儿子结点的可行性。
如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。
当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。
当扩展到叶节点时为问题的最优值。
structKNAPNODE//状态结构体
bools1[N];
//当前放入物体
intk;
//搜索深度
intb;
//价值上界
//物体重量
//物体价值
};
structHEAP//堆元素结构体
KNAPNODE*p;
//结点数据
//所指结点的上界
//交换两个堆元素
voids&
a,HEAP&
b）
HEAPtemp=a;
a=b;
b=temp;
//堆中元素上移
voidmov_up（HEAPH[],inti）
booldone=false;
if（i!
=1）{
while（!
done&
i!
if（H[i].b>
H[i/2].b）{
swap（H[i],H[i/2]）;
}else{
done=true;
i=i/2;
//堆中元素下移
voidmov_down（HEAPH[],intn,inti）
if（（2*i）<
=n）{
（（i=2*i）<
=n））{
if（i+1<
=n&
H[i+1].b>
H[i].b）{
i++;
if（H[i/2].b<
H[i].b）{
swap（H[i/2],H[i]）;
//往堆中插入结点
voidinsert（HEAPH[],HEAPx,int&
n）
n++;
H[n]=x;
mov_up（H,n）;
//删除堆中结点
voiddel（HEAPH[],int&
n,inti）
HEAPx,y;
x=H[i];
y=H[n];
n--;
if（i<
H[i]=y;
if（y.b>
=x.b）{
mov_up（H,i）;
}else{
mov_down（H,n,i）;
//获得堆顶元素并删除
HEAPdel_top（HEAPH[],int&
HEAPx=H[1];
del（H,n,1）;
returnx;
//计算分支节点的上界
voidbound（KNAPNODE*node,intM,goodsa[],intn）
inti=node->
k;
floatw=node->
w;
floatp=node->
p;
if（node->
w>
M）{//物体重量超过背包载重量
node->
b=0;
//上界置为0
}else{
while（（w+a[i].w<
=M）&
（i<
n））{
w+=a[i].w;
//计算背包已装入载重
p+=a[i++].p;
//计算背包已装入价值
if（i<
n）{
node->
b=p+（M-w）*a[i].p/a[i].w;
node->
b=p;
//用分支限界法实现0/1背包问题
intKnapSack4（intn,goodsa[],intC,intX[]）
inti,k=0;
//堆中元素个数的计数器初始化为0
intv;
KNAPNODE*xnode,*ynode,*znode;
HEAPx,y,z,*heap;
heap=newHEAP[n*n];
//分配堆的存储空间
for（i=0;
i<
i++）{
a[i].sign=i;
//记录物体的初始编号
//对物体按照价值重量比排序
xnode=newKNAPNODE;
//建立父亲结点
i++）{//初始化结点
xnode->
s1[i]=false;
xnode->
k=xnode->
w=xnode->
p=0;
while（xnode->
n）{
ynode=newKNAPNODE;
//建立结点y
*ynode=*xnode;
//结点x的数据复制到结点y
ynode->
s1[ynode->
k]=true;
//装入第k个物体
w+=a[ynode->
k].w;
//背包中物体重量累计
p+=a[ynode->
k].p;
//背包中物体价值累计
k++;
//搜索深度++
bound（ynode,C,a,n）;
//计算结点y的上界
y.b=ynode->
b;
y.p=ynode;
insert（heap,y,k）;
//结点y按上界的值插入堆中
znode=newKNAPNODE;
//建立结点z
*znode=*xnode;
//结点x的数据复制到结点z
znode->
k++;
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->
i++）{//取装入背包中物体在排序前的序号
if（xnode->
s1[i]）{
X[a[i].sign]=1;
X[a[i].sign]=0;
deletexnode;
deleteheap;
returnv;
//返回背包中物体的价值
/*测试以上算法的主函数*/
intsum4=KnapSack4（n,a,C,X）;
//调用分支限界法求0/1背包问题
分支限界法求解0/1背包问题:
sum4）;
return0;
分支限界法求解0/1背包问题的时间复杂度为：
相同的数据，求相同同的问题，用不同的方法，得到的结果，所得结果
正式所求问题的最优解，所编程序是正确的。
五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：
1.本实验中4种算法要用同一个主函数调用，由于背包容量、物品、解向量等变量都是以全局变量定义的，每次调用一种算法之前，必须要看这些重要的变量值是否因上一个算法的调用而发生了改变，如发生改变，则需将其改回原值，使得各种算法之间互不影响。
2.在本实验中，各种算法因申请存储空间等原因，运行时间的排序不可能与其时间复杂度的一致，甚至可能会有很大差别，又不可能输入大量数据进行各种算法的测试，所以没有求各算法的运行时间并进行比较。
即各算法的运行时间受较多因素影响，较小数据量时与算法时间复杂度无相关性，比较是没有意义的
升级会员 