背包问题算法设计提高性实验Word文档格式.docx
《背包问题算法设计提高性实验Word文档格式.docx》由会员分享，可在线阅读，更多相关《背包问题算法设计提高性实验Word文档格式.docx（13页珍藏版）》请在冰点文库上搜索。
0,wi>
0,vi>
0,0<
=i<
=n，要求找到一个n元的0-1向量（x1,x2,...,xn）,使得：
maxsum_{i=1ton}（vi*xi）,且满足如下约束：
1）sum_{i=1ton}（wi*xi）<
=c
2）xi∈{0,1},1<
=n
（2）0-1背包问题的求解
0-1背包问题具有最优子结构性质和子问题重叠性质，适于采用动态规划方法求解
●最优子结构性质
设（y1,y2,...,yn）是给定0-1背包问题的一个最优解，则必有结论，（y2,y3,...,yn）是如下子问题的一个最优解：
maxsum_{i=2ton}（vi*xi）
sum_{i=2ton}（wi*xi）<
=c-w1*y1
xi∈{0,1},2<
因为如若不然，则该子问题存在一个最优解（z2,z3,...,zn），而（y2,y3,...,yn）不是其最优解。
那么有：
sum_{i=2ton}（vi*zi）>
sum_{i=2ton}（vi*yi）且，w1*y1+sum_{i=2ton}（wi*zi）<
=c进一步有：
v1*y1+sum_{i=2ton}（vi*zi）>
sum_{i=1ton}（vi*yi）w1*y1+sum_{i=2ton}（wi*zi）<
=c这说明：
（y1,z2,z3,...zn）是所给0-1背包问题的更优解，那么说明（y1,y2,...,yn）不是问题的最优解，与前提矛盾，所以最优子结构性质成立。
●子问题重叠性质
设所给0-1背包问题的子问题p（i,j）:
maxsum_{k=iton}（vk*xk）
（1）sum_{k=iton}（wk*xk）<
=j
（2）xk∈{0,1},i<
=k<
问题p（i,j）是背包容量为j、可选物品为i,i+1,...,n时的子问题,设m（i,j）是子问题p（i,j）的最优值，即最大总价值。
则根据最优子结构性质，可以建立m（i,j）的递归式：
a.递归初始m（n,j）背包容量为j、可选物品只有n，若背包容量j大于物品n的重量，则直接装入；
否则无法装入。
m（n,j）=vn,j>
=wn
m（n,j）=0,0<
=j<
wn
b.递归式m（i,j）背包容量为j、可选物品为i,i+1,...,n如果背包容量j<
wi，则根本装不进物品i，所以有：
m（i,j）=m（i+1,j）,0<
wi
如果j>
=wi，则在不装物品i和装入物品i之间做出选择,不装物品i的最优值：
m（i+1,j）,装入物品i的最优值：
m（i+1,j-wi）+vi,所以：
m（i,j）=max{m（i+1,j）,m（i+1,j-wi）+vi},j>
=wi。
2、分支限界法求解0-1背包问题
（1）问题描述：
已知有n个物品和一个可以容纳m重量的背包，每种物品i的重量为weight，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。
（2）设计思想与分析：
对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。
四、实验方案或步骤
1、动态规划法求解0/1背包问题
#include<
stdio.h>
#include"
iostream"
usingnamespacestd;
intmax（inta,intb）
{
if（a>
b）
returna;
else
returnb;
}
voidZeroOneBag（int*v,int*w,int*x,intc,intn,intm[8][100]）
inti,j;
for（j=0;
j<
c;
j++）
{
if（j<
w[n]）//从第N件物品开始，如果放不下
m[n][j]=0;
else//如果放的下
m[n][j]=v[n];
for（i=n-1;
i>
=1;
i--）//控制物品的循环,从i-1到第1件
for（j=0;
w[i];
j++）//贪心法把此行注释
m[i][j]=m[i+1][j];
//贪心法把此行注释
for（j=w[i];
j<
=c;
j++）
m[i][j]=max（m[i+1][j],m[i+1][j-w[i]]+v[i]）;
for（i=1;
i<
n;
i++）//构造最优解
if（m[i][c]==m[i+1][c]）
x[i]=0;
x[i]=1;
c=c-w[i];
x[n]=（m[n][c]）?
1:
0;
//m[n][c]大于0吗？
大于就是选了
return;
voidmain（）
inti=0,n=7;
intw[]={0,2,3,5,7,1,4,1};
intv[]={0,10,5,15,7,6,18,3};
intx[]={0,0,0,0,0,0,0,0};
cout<
<
"
程序自带数据为：
\n"
;
编号重量价值"
endl;
for（i=0;
i<
n;
i++）
"
i+1<
w[i+1]<
v[i+1]<
intm=15;
intarray[8][100]={0};
ZeroOneBag（v,w,x,m,7,array）;
\n背包能装的最大价值为:
array[1][m];
\n\n最优解为:
=n;
i++）
x[i]<
\n\n"
system（"
pause"
）;
2、分支限界法求解0/1背包问题
#include<
#include<
malloc.h>
#defineMaxSize100//最多结点数
typedefstructQNode
{
floatweight;
floatvalue;
intceng;
structQNode*parent;
boolleftChild;
}QNode,*qnode;
//存放每个结点
typedefstruct
qnodeQ[MaxSize];
intfront,rear;
}SqQueue;
//存放结点的队列
SqQueuesq;
floatbestv=0;
//最优解
intn=0;
//实际物品数
floatw[MaxSize];
//物品的重量
floatv[MaxSize];
//物品的价值
intbestx[MaxSize];
//存放最优解
qnodebestE;
voidInitQueue（SqQueue&
sq）//队列初始化
sq.front=1;
sq.rear=1;
}
boolQueueEmpty（SqQueuesq）//队列是否为空
if（sq.front==sq.rear）
returntrue;
else
returnfalse;
voidEnQueue（SqQueue&
sq,qnodeb）//入队
if（sq.front==（sq.rear+1）%MaxSize）
printf（"
队列已满!
return;
sq.Q[sq.rear]=b;
sq.rear=（sq.rear+1）%MaxSize;
qnodeDeQueue（SqQueue&
sq）//出队
qnodee;
队列已空!
return0;
e=sq.Q[sq.front];
sq.front=（sq.front+1）%MaxSize;
returne;
voidEnQueue1（floatwt,floatvt,inti,QNode*parent,boolleftchild）
qnodeb;
if（i==n）//可行叶子结点
if（vt==bestv）
{
bestE=parent;
bestx[n]=（leftchild）?
}
return;
b=（qnode）malloc（sizeof（QNode））;
//非叶子结点
b->
weight=wt;
value=vt;
ceng=i;
parent=parent;
leftChild=leftchild;
EnQueue（sq,b）;
}
voidmaxLoading（floatw[],floatv[],intc）
floatwt=0;
floatvt=0;
inti=1;
//当前的扩展结点所在的层
floatew=0;
//扩展节点所相应的当前载重量
floatev=0;
//扩展结点所相应的价值
qnodee=NULL;
qnodet=NULL;
InitQueue（sq）;
EnQueue（sq,t）;
//空标志进队列
while（!
QueueEmpty（sq））
{
wt=ew+w[i];
vt=ev+v[i];
if（wt<
=c）
if（vt>
bestv）
bestv=vt;
EnQueue1（wt,vt,i,e,true）;
//左儿子结点进队列
}
EnQueue1（ew,ev,i,e,false）;
//右儿子总是可行；
e=DeQueue（sq）;
//取下一扩展结点
if（e==NULL）
if（QueueEmpty（sq））break;
EnQueue（sq,NULL）;
//同层结点尾部标志
e=DeQueue（sq）;
i++;
ew=e->
weight;
//更新当前扩展结点的值
ev=e->
value;
printf（"
最优取法为：
for（intj=n-1;
j>
j--）//构造最优解
bestx[j]=（bestE->
leftChild?
0）;
bestE=bestE->
parent;
for（intk=1;
k<
=n;
k++）
if（bestx[k]==1）
printf（"
\n物品%d:
重量：
%.1f，价值：
%.1f\n"
k,w[k],v[k]）;
最优价值为：
%.1f\n\n"
bestv）;
voidmain（）
intc;
floatewv[MaxSize];
////////////////////0-1背包问题分枝限界法/////////////////////\n\n"
请输入物品的数量：
scanf（"
%d"
&
n）;
请输入背包的最大承重量：
c）;
\n请输入物品的重量和单位重量价值:
for（inti=1;
物品%d:
i）;
scanf（"
%f%f"
w[i],&
ewv[i]）;
v[i]=w[i]*ewv[i];
maxLoading（w,v,c）;
五、实验结果与分析
1、动态规划算法运行结果
2.、分支限界算法运行结果
六、讨论
解决0/1背包问题的方法有多种，最常用的有贪心法和动态规划法。
其中贪心法无法得到问题的最优解，而动态规划法都可以得到最优解。
动态规划算法的基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。
在最坏情况下，动态规划算法的空间复杂度是O（2n），时间复杂度也为O（2n）。
而利用分支限界法求解0/1背包问题的关键是设计上下界函数，最优解是以目标函数取最大值为最优解，它采用二叉树形式的状态空间数，每个结点只有左右两个孩子，广度优先在这里表现为考察一个结点的左右孩子，最终求出最优解。
通过本实验让我学到了不同方法求解0/1背包问题的原理以及其各自的优缺点，同是让我对算法设计有了更深的理解，对其设计原理也有了更透彻更深入的理解。
七、教师评语与实验成绩
实验成绩
教师签名
日期
升级会员 