蛮力法动归贪心分支限界法解01背包问题Word格式文档下载.docx
《蛮力法动归贪心分支限界法解01背包问题Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《蛮力法动归贪心分支限界法解01背包问题Word格式文档下载.docx（31页珍藏版）》请在冰点文库上搜索。
1.5算法描述
算法的伪代码描述如下：
输入：
背包的容量c,物品的个数n,n个物品的重量w[n],价值v[n]
输出：
装入背包的物品编号以及产生的最大价值
1.初始化最大价值max=0,结果子集s=φ;
2.对集合{1,2,......n}的每一个子集T，执行下述操作：
2.1初始化背包的价值v=0，背包的重量w=0;
2.2对子集t的每一个元素j
2.2.1如果w+wj<
c,则w=w+wj,v=v+vj;
2.2.2否则，转步骤2考察下一个子集；
2.3如果max<
v,则max=v;
s=t;
3.输出子集S中的各元素
2、动态规划法
2.1数据结构
该程序不涉及任何数据结构
2.2函数组成
intmax（inti,intj）;
比较并返回两个数中的较大值
intKnapSack（intw[],intv[],intx[],intn,intc）;
求解背包取得的最大值
2.3输入/输出设计
2.4符号名说明
w[]
物品的重量
v[]
物品的价值
x[]
物品的选择情况
V[][]
存放迭代结果
2.5算法描述
背包的容量c,物品的个数n,n个物品的重量w[n],价值v[n]
装入背包的物品标号和背包获得的最大价值
1.初始化二维数组V[][]={0}
2.初始化二维数组的第0行，第0列
2.循环直到i==n
2.1循环直到j=c
2.1.1如果背包的容量不足以装入物品i,则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值相等
2.2.2如果背包的容量可以装入物品i,分别计算装入物品i可达到的价值量V[i-1][j-w[i]]+v[i],以及不放入物品i可以得到的最大价值V[i-1][j]，取二者中的较大者作为把前i个物品装入容量为j的背包中的最优解
3、贪心法
3.1数据结构
注：
结构体用来存放物品的重量、价值、单位价值、物品编号等信息
struct_Object
intValue;
//物品价值
intWeight;
//物品重量
doubleAveValue;
//物品单位价值
doubleNum;
//物品可以放入的数量
intkey;
//物品标号
3.2函数组成
intPartition（_Objectr[],intfirst,intend）；
以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标
voidQuickSort（_Objectr[],intfirst,intend）；
快速排序
doubleknaspsack（intn,intM,_Objectobject[]）；
求解背包问题的最优解
3.3输入/输出设计
3.4符号名说明
pro[]
物品的重量、价值、单位价值、编号
3.5算法描述
算法的伪代码描述如下：
背包的容量c,物品的个数n,n个物品的重量pro[n].Weight,价值pro[n].Value
输出：
1.计算物品的单位价值并存入pro[n].
2.将物品按照单位价值递减的顺序进行排序
3.i=0;
4.循环直到（object[i].Weight>
c）
4.1将第i个物品放入背包,object[i].Num=1；
4.2c-=pro[n].Weight；
4.3i++；
5.记录最后放入背包的物品的重量：
object[i].Num=（double）C/object[i].Weight；
4、分支限界法
4.1数据结构
注：
物品结构体，存放物品价值、重量、单位价值、物品编号等信息
structobj
doubleavg;
intid;
//物品编号
结构体node用来存放节点表节点
structnode
node*parent,//父亲结点指针
*next;
//后继结点指针
intlevel,//节点所处的层
isin,//记录物品是否装入背包，0代表不装,1代表装入
cw,//当前背包已经装入的物品重量
cv;
//当前背包已经装入的物品价值
doubleub;
//结点的上界值
4.2函数组成
doubleUpb（inti,intcw,intcv）;
//计算上界值
node*nnoder（node*parent1,intisin1,doubleub1）;
生成一个新的结点
voidaddnode（node*node1）;
//将结点添加到队列中
node*nextnode（）;
//取下一个结点
voidfenzjx（）;
//分支界限法的主要实现函数
voidoutput（）;
//用于输出物品的选择情况及最优解
4.3输入/输出设计
4.4符号名说明
c
背包的容量
pro
存放物品信息
avg
物品的单位价值量
opv
背包容量最优解
popv
指向最优解的指针
level
节点的层
cw
当前背包装载量
cv
当前背包价值
ub
节点的上界值
isin
记录当前结点物品是否放入背包
物品原来位置
（4）算法描述
背包的容量c,物品的个数n,n个物品的信息pro[n]
1.对输入的物品按照单位价值量递减的顺序进行排序
2.初始化问题最优解opv=0,初始化第0层结点，计算上界值ub=Upb（0,0,0）;
并设置该结点设为优先级队列的根结点
3.循环直到优先级队列为空
3.1如果取出当前结点位于第n-1层，则其子结点已是叶子结点，判断子结点取值情况，若得到的解大于当前问题得到的最优解opv，则重置问题的最优解opv
3.2如果取出当前结点层level<
n-1
对结点i的每个孩子结点x执行下列操作:
3.2.1如果结点x可能产生的最优解ub<
opv，则丢弃该结点;
3.2.2否则估算该节点x的目标函数值ub,将结点加入队列;
4.将该结点对应的最优值输出，回溯求得最优解的各个分量
三、源程序及注释：
1、蛮力法
#include<
iostream>
math.h>
usingnamespacestd;
//物品
typedefstructobj
{
};
//生成子集
voidsubset（ints[][10],intn）
inti,j,m,k;
for（i=0;
i<
pow（2,n）;
i++）
k=i;
for（j=n-1;
j>
=0;
j--）
{
m=k%2;
s[i][j]=m;
k=k/2;
}
}
}
//判断子集可行性
voidjudge（ints[][10],objobj[],intmark[],intn,intc）
inti,j,v,w;
w=0;
v=0;
for（j=0;
j<
n;
j++）
{
w+=obj[j].w*s[i][j];
v+=obj[j].v*s[i][j];
}
if（w<
=c）
mark[i]=v;
else
mark[i]=0;
//求问题的最优解
intgetmax（intmark[],intn,int&
flag）
inti,max;
max=0;
if（mark[i]>
max）
max=mark[i];
flag=i;
returnmax;
//输出选择物品的情况
voidoutputObj（intflag,ints[][10],intn）
cout<
<
"
装入背包物品的编号为：
"
;
for（inti=0;
if（s[flag][i]==1）
cout<
i+1<
endl;
intmain（）
ints[1024][10],mark[1024],n,max,c,flag;
objobj[10];
请输入背包的容量：
cin>
>
c;
请输入物品的个数：
请分别输入物品的重量：
obj[i].w;
请分别输入物品的价值：
obj[i].v;
subset（s,n）;
judge（s,obj,mark,n,c）;
max=getmax（mark,n,flag）;
outputObj（flag,s,n）;
背包可容纳的最大价值为：
max<
return0;
2、动态规划法
//比较并返回两个数中的较大值
intmax（inti,intj）
if（i<
j）
returnj;
else
returni;
//求解背包取得的最大值
intKnapSack（intw[],intv[],intx[],intn,intc）
inti,j,V[105][1005]={0};
=n;
i++）//初始化第0列
V[i][0]=0;
=c;
j++）//初始化第0行
V[0][j]=0;
for（i=1;
i++）//计算第i行，进行第i次迭代
for（j=1;
if（j<
w[i]）
V[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=c,i=n;
i>
0;
i--）//求装入背包的物品编号
if（V[i][j]>
V[i-1][j]）
x[i]=1;
j=j-w[i];
elsex[i]=0;
returnV[n][c];
intc,n,w[105],v[105],x[105],max;
//x[]记录物品的选择情况
请输入背包的重量：
cin>
for（inti=1;
w[i];
for（i=1;
v[i];
max=KnapSack（w,v,x,n,c）;
cout<
装入背包的物品编号为：
if（x[i]==1）
3、贪心法
stdio.h>
//物品结构体
struct_Object
//划分
intPartition（_Objectr[],intfirst,intend）{
inti=first,j=end;
while（i<
while（i<
j&
&
r[i].AveValue>
r[j].AveValue）
j--;
if（i<
_Objecttemp=r[i];
r[i]=r[j];
r[j]=temp;
i++;
j&
_Objecttemp=r[i];
returni;
//快速排序
voidQuickSort（_Objectr[],intfirst,intend）{
intpivot;
if（first<
end）{
pivot=Partition（r,first,end）;
QuickSort（r,first,pivot-1）;
QuickSort（r,pivot+1,end）;
doubleknaspsack（intn,intM,_Objectobject[]）//n为物品个数，M为背包容量
{
inti;
intC=M;
doublemaxValue=0;
object[i].Weight<
C;
object[i].Num=1;
//初始化放入背包的物品为0
maxValue+=object[i].Value;
C=C-object[i].Weight;
object[i].Num=（double）C/object[i].Weight;
maxValue+=object[i].Num*object[i].Value;
returnmaxValue;
intn,c;
_Objectpro[1001];
背包的容量：
请分别输入物品的重量和价值：
for（inti=0;
pro[i].Weight>
pro[i].Value;
pro[i].AveValue=（double）pro[i].Value/pro[i].Weight;
pro[i].Num=0;
pro[i].key=i;
QuickSort（pro,0,n-1）;
doublemaxValue=knaspsack（n,c,pro）;
背包的可容纳的最大价值为：
printf（"
%.2f"
maxValue）;
intk;
各个物品装入背包的重量分别为：
for（k=0;
k<
k++）
for（intj=0;
if（pro[j].key==k）//找到原来顺序的物品编号
pro[j].Weight*pro[j].Num<
4、分支限界法
#include<
cstdio>
conio.h>
iomanip>
stdlib.h>
usingnamespacestd;
structobj{
//节点结构体
structnode
intPartition（objr[],intfirst,intend）{
r[i].avg>
r[j].avg）
objtemp=r[i];
objtemp=r[i];
voidQuickSort（objr[],intfirst,intend）{
classfzjx{
private:
node*front,//队首指针
*first,//根节点指针
*popv;
//解结点指针
doubleopv;
//背包可产生的最大价值
obj*pro;
intn,//物品个数
c;
//背包容量
public:
fzjx（obj*pro1,intw1,intn1）;
~fzjx（）;
int*flag;
fzjx:
:
fzjx（obj*pro1,intc1,intn1）
n=n1;
c=c1;
pro=newobj[n];
flag=newint[n];
pro[i].w=pro1[i].w;
pro[i].v=pro1[i].v;
pro[i].id=pro1[i].id;
pro[i].avg=pro1[i].avg;
flag[i]=i;
front=newnode[1];
front->
next=NULL;
opv=0;
popv=newnode[1];
popv=NULL;
~fzjx（）
delete[]first;
delete[]front;
delete[]popv;
delete[]pro;
doublefzjx:
Upb（inti,intcw,intcv）
intcleft=c-cw;
doublev=（double）cv;
if（i<
n）
v+=1.0*pro[i].avg*cleft;
returnv;
node*fzjx:
nnoder（node*parent1,intisin1,doubleub1）
{//生成一个新结点
node*node2=new（node）;
node2->
parent=parent1;
node2
升级会员 