蛮力法等求解背包问题报告剖析.docx
《蛮力法等求解背包问题报告剖析.docx》由会员分享，可在线阅读，更多相关《蛮力法等求解背包问题报告剖析.docx（28页珍藏版）》请在冰点文库上搜索。
蛮力法等求解背包问题报告剖析
算法综合实验报告
学号：
姓名：
一、实验内容：
分别用蛮力、动态规划、贪心及分支限界法实现对TSP问题或者0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。
二、程序设计的基本思想、原理和算法描述：
1、蛮力法
（1）数据结构:
使用一维数组存储物品的价值和重量还有下标。
（2）函数组成
除主函数外还有一个subset（）函数，在此函数中列出所有的子集列出子集的同时求解最大价值，并且物品总重量要小于背包总容量。
（3）输入/输出设计
首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。
最后输出物品的最大价值。
本程序通过键盘进行输入、屏幕进行输出。
（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）
（4）符号名说明
w[1001]为物品重量的集合，v[1001]为物品价值的集合，n为物品数量，m为背包总容量,x[1001]用来存储物品是否装入背包，0为不装入，1为装入。
用a[1001]来存储下标，用下标找出所有子集。
（5）算法描述
采用增量构造的方法来构造出物品的所有子集，对物品的下标应用此方法进行构造，下标与物品相对应，选出子集时物品的重量加之前重量小于背包总重量时将价值加上去，最后选出能装入背包的物品的最大值。
2、动态规划法
（1）数据结构：
使用一维数组存储各个物品价值，重量，使用一个二维数组存储动态规划的整体求解的表，并以背包容量为最大列号，物品个数为最大行号。
（2）函数组成：
除主函数外由两个函数组成，一个是求解两个数中的大的一个的函数，另一个则是进行动态规划求解的函数，在使用动态规划方法具体求解时调用求最大值函数，在主程序之中调用动态规划函数。
（3）输入/输出设计：
首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。
输出物品的最大价值。
本程序通过键盘进行输入、屏幕进行输出。
（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）
（4）符号名说明：
w[1001]为物品重量的集合，v[1001]为物品价值的集合，n为物品数量，m为背包总容量,x[1001]用来存储物品是否装入背包，0为不装入，1为装入。
V[1001][1001]用来存储动态规划具体求解过程,V[n][m]为最终结果最大价值。
（5）算法描述：
[1].背包容量不足以装入物品i，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，则x[i]=0，背包不增加价值。
[2].背包容量可以装入物品i，如果把第i个物品装入背包，则背包中物品的价值等于前i-1个物品装入容量为j-w[i]的背包中的价值加上第i个物品的价值；如果第i个物品没有装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j的背包中所取得的价值。
取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。
表示在前
个物品中能够装入容量为
的背包中的物品的最大值，则可以得到如下动态函数：
3、贪心法
（1）数据结构：
定义多个一维数组存储数据进行贪心选择。
（2）函数组成：
编写了一个选择排序函数，一个判断是否能装入包中的函数，一个主函数，在主函数中调用判断函数，在判断函数初始调用排序函数将单位价值重量从大到小进行排序。
（3）输入/输出设计：
首先通过键盘输入物品的总重量，再输入背包总容量，依次输入每个物品的重量，对应输入相应重量的价值，循环直至输入所有物品的重量和价值。
先输出放入背包中的物品序号，在输出总价值，最后输出背包总容量。
本程序通过键盘进行输入、屏幕进行输出。
（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）
（4）符号名说明:
w[1001]为物品重量的集合，v[1001]为物品价值的集合，a[1001]为单位物品价值集合,n为物品数量，m为背包总容量,x[1001]用来存储物品是否装入背包，0为不装入，1为装入。
（5）算法描述：
制定贪心策略，求出单位物品价值并从大到小进行排序，依照排序结果从大到小放入，知道物品重量大于背包剩余容量为止，但是求出的并不是最优解，贪心法无法求出0/1背包的最优解，只能求出背包问题的最优解。
4、分支限界法
（1）数据结构
定义一个优先队列存储分支限界所使用的树的节点，使用一维数组存储物品的重量和价值。
（2）函数组成
一个构造函数，申请动态数组构造树，一个析构函数，删掉动态申请的数组，一个计算上界的函数，一个生成新节点的函数，一个将节点加入优先队列的函数，一个取上界最大节点的函数，一个背包问题求解的函数，一个显示函数，在主函数中调用函数求解。
本程序还使用了类和结构体。
（3）输入/输出设计
通过键盘先输入背包总容量，再输入物品总数，依次输入每个物品的重量，依次输入每个物品的价值。
输出最大价值以及每个物品是否装入背包中
本程序通过键盘进行输入、屏幕进行输出。
（根据实际程序情况，还可以选择随机产生输入数据、将输出数据输出到文件等其它方式）
（4）符号名说明
Cw为当前背包装载量，cv为当前背包价值，ub节点的上界值，c为背包的容量，n为物品数量，x[]记录物品是否放入背包，0为不放入，1为放入，w[]为存放物品重量的数组，v[]为存放物品价值的数组。
（5）算法描述
给定n种物品和一个容量为C的背包,物品i的重量是Wi,其价值为Vi,0/1背包问题是如何选择装入背包的物品（物品不可分割）,使得装入背包中物品的总价值最大，一般情况下,解空间树中第i层的每个结点,都代表了对物品1～i做出的某种特定选择,这个特定选择由从根结点到该结点的路径唯一确定:
左分支表示装入物品,右分支表示不装入物品。
对于第i层的某个结点,假设背包中已装入物品的重量是w,获得的价值是v,计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v,加上背包剩余容量W-w与剩下物品的最大单位重量价值vi+1/wi+1的积,于是,得到限界函数:
ub=v+（W-w）×（vi+1/wi+1）
根据限界函数确定目标函数的界[down,up]，然后,按照广度优先策略遍历问题的空间树。
三、源程序及注释：
1、蛮力法
#include
#include
usingnamespacestd;
intx[1001]={0};
intw[1001],v[1001];
intmaxValue=0;
intsubset（intn,intm,int*A,intcur）//n是数组长度,A为待求子集数组，cur用于递归记录
{
intweight=0;
intvalue=0;
for（inti=0;i{
//printf（"%d",A[i]）;
if（weight+w[A[i]]{
x[A[i]]=1;
weight=weight+w[A[i]];
value=value+v[A[i]];
}
}
if（maxValuemaxValue=value;
//printf（"\n"）;
ints=cur?
A[cur-1]+1:
0;//判断cur是否是0，避免越界,是0的话就取s=0，非零的话s=A[cur-1]
for（i=s;i{
A[cur]=i;
subset（n,m,A,cur+1）;
}
returnmaxValue;
}
intmain（）
{
intn,m;
inta[1000];
cout<<"请输入物品总数量:
"<cin>>n;//输入物品总数量
cout<<"请输入背包总容量:
"<cin>>m;//输入背包总容量
cout<<"请依次输入物品的重量和价值"<for（inti=0;i{
cin>>w[i];
cin>>v[i];
a[i]=i;//记录下标
}
cout<<"总价值为:
"<return0;
}
2、动态规划法
#include
#include
usingnamespacestd;
intV[1002][1002];
intw[1001],v[1001];
intmax（intxx,intyy）//判断两个数谁大，返回大的那个值
{
if（xx>=yy）
returnxx;
else
returnyy;
}
intKnapSack（int*w,int*v,intn,intm）
{
intx[1001]={0};
inti,j;
for（i=0;i<=n;i++）//初始化第0列为0
V[i][0]=0;
for（j=0;j<=m;j++）//初始化第0行为0
V[0][j]=0;
for（i=1;i<=n;i++）//在背包能放下的情况下，如果放入后比i-1个物品装入后价值还小则不放入
for（j=1;j<=m;j++）//计算第i行，进行第i次迭代
{
if（jV[i][j]=V[i-1][j];
else
V[i][j]=max（V[i-1][j],（V[i-1][j-w[i]]+v[i]））;
}
for（j=m,i=n;i>0;i--）//求装入背包的物品
{
if（V[i][j]>V[i-1][j]）
{
x[i]=1;
j=j-w[i];
}
else
x[i]=0;
}
returnV[n][m];//返回背包取得的最大价值
}
intmain（）
{
intn,m;//n为物品数量，m为背包容量
inti;
intmaxValue;
cout<<"请输入物品数量"<cin>>n;
cout<<"请输入背包容量"<cin>>m;
cout<<"请依次输入每个物品的重量和价值（注：
重量在前，价值在后）"<for（i=1;i<=n;i++）
{
cin>>w[i];
cin>>v[i];
}
maxValue=KnapSack（w,v,n,m）;
cout<<"最大价值是：
"<return0;
}
3、贪心法：
#include
#include
usingnamespacestd;
intn,m;
intw[1001],v[1001];
doublea[1001];
intmaxValue=0;
intb[1001];//存储物品序号
intx[1001]={0};//0为不放入背包，1为放入背包
voidSort（intn,double*a,int*w,int*v,int*b）//排序函数
{
for（inte=0;efor（intt=n-1;t>e;t--）{
if（a[e]{
inttemp=a[e];
intq=w[e];
ints=v[e];
intp=b[e];
a[e]=a[t];
a[t]=temp;
w[e]=w[t];
w[t]=q;
v[e]=v[t];
v[t]=s;
b[e]=b[t];
b[t]=p;
}
}
}
intKnapSack（intn,intm,int*w,int*v,int*x）//判断是否能装入背包
{
Sort（n,a,w,v,b）;
for（intj=0;w[j]x[j]=1;
maxValue=maxValue+v[j];
m=m-w[j];
}
returnmaxValue;
}
intmain（）{
cin>>n;//输入物品总个数
cin>>m;//输入背包总容量
intweight=0;
for（inti=0;icin>>w[i];//输入物品重量
cin>>v[i];//输入物品价值
a[i]=v[i]/w[i];//求得单位重量价值
b[i]=i+1;//记录物品序号
}
maxValue=KnapSack（n,m,w,v,x）;
for（intj=0;j{
if（x[j]==1）
{
cout<<"第"<weight=weight+w[j];
}
}
cout<cout<cout<<"总重量为：
"<return0;
}
5、分支限界法
#include
#include
usingnamespacestd;
int*x;
structnode
{//结点表结点数据结构
node*parent,//父结点指针
*next;//后继结点指针
intlevel,//结点的层
bag,//节点的解
cw,//当前背包装载量
cv;//当前背包价值
floatub;//结点的上界值
};
classKnap
{
private:
structnode*front,//队列队首
*bestp,*first;//解结点、根结点
int*v,*w,n,c,*M;//背包价值、重量、物品数、背包容量、记录大小顺序关系
longlbestp;//背包容量最优解
public:
voidSort（）;
Knap（int*pp,int*ww,intcc,intnn）;
~Knap（）;
floatBound（inti,intcw,intcv）;//计算上界
node*nnoder（node*pa,intba,floatuub）;//生成一个结点ba=1生成左节点ba=0生成右节点
voidaddnode（node*nod）;//将结点添加到队列中
voiddeletenode（node*nod）;//将结点队列中删除
structnode*nextnode（）;//取下一个节点
voiddisplay（）;//输出结果
voidsolvebag（）;//背包问题求解
};
Knap:
:
Knap（int*pp,int*ww,intcc,intnn）//构造函数
{
inti;
n=nn;
c=cc;
v=newint[n];//动态申请数组
w=newint[n];
M=newint[n];
for（i=0;i{
v[i]=pp[i];
w[i]=ww[i];
M[i]=i;
}
front=newnode[1];
front->next=NULL;
lbestp=0;
bestp=newnode[1];
bestp=NULL;
Sort（）;
}
Knap:
:
~Knap（）//析构函数
{
delete[]first;
delete[]front;
delete[]bestp;
delete[]v;
delete[]w;
}
floatKnap:
:
Bound（inti,intcw,intcv）
{//计算上界
intleft=c-cw;
floatb=（float）cv;
while（i{
left-=w[i];
b+=v[i];
i++;
}
if（ireturnb;
}
node*Knap:
:
nnoder（structnode*pa,intba,floatuub）
{//生成一个新结点
node*nodell=new（node）;
nodell->parent=pa;
nodell->next=NULL;
nodell->level=（pa->level）+1;
nodell->bag=ba;
nodell->ub=uub;
if（ba==1）
{
nodell->cw=pa->cw+w[pa->level];
nodell->cv=pa->cv+v[pa->level];
}
else
{
nodell->cw=pa->cw;
nodell->cv=pa->cv;
}
return（nodell）;
}
voidKnap:
:
addnode（node*no）
{//将结点加入优先队列
node*p=front->next,*next1=front;
floatub=no->ub;
while（p!
=NULL）
{
if（p->ub{no->next=p;next1->next=no;break;}
next1=p;
p=p->next;
}
if（p==NULL）{next1->next=no;
}
}
node*Knap:
:
nextnode（）
{//取上限最大结点
node*p=front->next;
front->next=p->next;
return（p）;
}
voidKnap:
:
Sort（）
{
inti,j,k,kkl;
floatminl;
for（i=1;i{
minl=1.0*v[i]/w[i];
k=0;
for（j=1;j<=n-i;j++）
{
if（minl<1.0*v[j]/w[j]）
{
minl=1.0*v[j]/w[j];
swap（v[k],v[j]）;
swap（w[k],w[j]）;
swap（M[k],M[j]）;
k=j;
}
}
}
}
voidKnap:
:
display（）//显示函数
{
inti;
cout<<"最大价值是:
"<for（i=n;i>=1;i--）
{
x[M[i-1]]=bestp->bag;
bestp=bestp->parent;
}
cout<<"物品状态为（0为不装入，1为装入）:
"<for（i=1;i<=n;i++）
cout<<"x（"<}
voidKnap:
:
solvebag（）
{//背包问题求解
inti;
floatubb;
node*aa;
first=newnode[1];//根结点
first->parent=NULL;
first->next=NULL;
first->level=0;
first->cw=0;
first->cv=0;
first->bag=0;
ubb=Bound（0,0,0）;
first->ub=ubb;
front->next=first;
while（front->next!
=NULL）
{
aa=nextnode（）;
i=aa->level;
if（i==n-1）
{
if（aa->cw+w[i]<=c&&（long）（aa->cv+v[i]）>lbestp）
{
lbestp=aa->cv+v[i];
bestp=nnoder（aa,1,（float）lbestp）;
}
if（（long）（aa->cv）>lbestp）
{
lbestp=aa->cv;
bestp=nnoder（aa,0,（float）lbestp）;
}
}
if（i{
if（aa->cw+w[i]<=c&&Bound（i+1,
aa->cw+w[i],aa->cv+v[i]）>（float）lbestp）
{
ubb=Bound（i,aa->cw+w[i],aa->cv+v[i]）;
addnode（nnoder（aa,1,ubb））;
}
ubb=ubb=Bound（i,aa->cw,aa->cv）;
if（ubb>lbestp）
addnode（nnoder（aa,0,ubb））;
}
}
display（）;
}
voidmain（）
{
intc,n;
inti=0;
int*v;
int*w;
cout<<"请输入背包容量:
"<cin>>c;
cout<<"请输入物品数:
"<cin>>n;
x=newint[n];
v=newint[n];
w=newint[n];
cout<<"请输入"<"<for（i=0;icin>>w[i];
cout<<"请输入"<"<<
升级会员 