蛮力法、动归、贪心、分支限界法解01背包问题

算法综合实验报告

学 号： 1004121206

姓 名： 林

一、实验内容：

分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。

二、程序设计的基本思想、原理和算法描述：

1、 蛮力法 1.1数据结构

注：结构体obj用来存放单个物品的价值和重量

typedef struct obj {

int w;//物品的重量 int v;//物品的价值

};

1.2 函数组成

void subset(int s[][10],int n)：用来生成子集的函数

void judge(int s[][10], obj obj[],int mark[],int n,int c)：判断子集的可行性 int getmax(int mark[],int n,int &flag)：求解问题的最优解 void outputObj(int flag,int s[][10],int n):输出选择物品的情况 1.3 输入/输出设计

--精品

精品---

本程序通过键盘进行输入、屏幕进行输出。

1.4 符号名说明

符号 S[][] mark[] n c max flag

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--精品

精品---

3.输出子集S中的各元素 2、 动态规划法 2.1 数据结构

该程序不涉及任何数据结构 2.2 函数组成

int max(int i,int j);比较并返回两个数中的较大值

int KnapSack (int w[],int v[],int x[],int n,int c);求解背包取得的最大值

2.3 输入/输出设计

本程序通过键盘进行输入、屏幕进行输出。 2.4 符号名说明

符号 n c 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 {

int Value;//物品价值 int Weight;//物品重量

double AveValue;//物品单位价值 double Num;//物品可以放入的数量 int key;//物品标号 };

3.2 函数组成

--精品

精品---

int Partition(_Object r[],int first,int end)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标

void QuickSort(_Object r[],int first,int end)；快速排序

double knaspsack(int n,int M,_Object object[])；求解背包问题的最优解

3.3 输入/输出设计

本程序通过键盘进行输入、屏幕进行输出。 3.4 符号名说明

符号 n c 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.2 c-=pro[n].Weight； 4.3 i++；

5.记录最后放入背包的物品的重量： object[i].Num=(double)C/object[i].Weight；

4、 分支限界法 4.1数据结构

注：物品结构体，存放物品价值、重量、单位价值、物品编号等信息 struct obj {

int v;//物品价值 int w;//物品重量

double avg;//物品单位价值 int id;//物品编号 };

注：结构体node用来存放节点表节点 struct node {

node *parent,//父亲结点指针 *next;//后继结点指针 int level,//节点所处的层

isin,//记录物品是否装入背包，0代表不装,1代表装入 cw,//当前背包已经装入的物品重量

--精品

精品---

cv;//当前背包已经装入的物品价值 double ub;//结点的上界值 };

4.2函数组成

int Partition(_Object r[],int first,int end)；以数组第一个元素为准对数组进行一次划分并返回基准元素的位置坐标

void QuickSort(_Object r[],int first,int end)；快速排序 double Upb(int i,int cw,int cv);//计算上界值

node *nnoder(node * parent1,int isin1,double ub1);生成一个新的结点 void addnode(node *node1);//将结点添加到队列中 node *nextnode(); //取下一个结点

void fenzjx();//分支界限法的主要实现函数 void output();//用于输出物品的选择情况及最优解

4.3 输入/输出设计

本程序通过键盘进行输入、屏幕进行输出。 4.4 符号名说明

--精品

精品---

符号 c n pro avg opv popv level cw cv ub isin flag (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三、源程序及注释：

1、蛮力法

#include #include using namespace std; //物品 typedef struct obj { };

//生成子集

int w; int v;

--精品

精品---

void subset(int s[][10],int n) {

int i,j,m,k; }

//判断子集可行性

void judge(int s[][10], obj obj[],int mark[],int n,int c) {

int i,j,v,w;

for(i=0;iw=0;

for(i=0;ik=i;

for(j=n-1;j>=0;j--) { }

m=k%2; s[i][j]=m; k=k/2;

--精品

精品---

v=0; for(j=0;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;

} }

//求问题的最优解

int getmax(int mark[],int n,int &flag){ int i,max; max=0;

for(i=0;imax)

{

--精品

精品---

}

}

max=mark[i]; flag=i;

return max; }

//输出选择物品的情况

void outputObj(int flag,int s[][10],int n) { } int main() {

int s[1024][10],mark[1024],n,max,c,flag; obj obj[10];

cout<<\"装入背包物品的编号为： \"; for(int i=0;icout<if(s[flag][i]==1)

cout<--精品

精品---

cout<<\"请输入背包的容量：\"; cin>>c;

cout<<\"请输入物品的个数：\"; cin>>n;

cout<<\"请分别输入物品的重量：\"; for(int i=0;icin>>obj[i].w;

}

cout<<\"请分别输入物品的价值：\"; for(i=0;icin>>obj[i].v;

} subset(s,n); judge(s,obj,mark,n,c); max=getmax(mark,n,flag); outputObj(flag,s,n);

cout<<\"背包可容纳的最大价值为： \"<2、动态规划法

--精品

精品---

#include using namespace std;

//比较并返回两个数中的较大值 int max(int i,int j) { if(ireturn j;

else

return i;

}

//求解背包取得的最大值

int KnapSack (int w[],int v[],int x[],int n,int c) { int i,j,V[105][1005]={0};

for(i=0;i<=n;i++)

V[i][0]=0; for(j=0;j<=c;j++)

V[0][j]=0;

for(i=1;i<=n;i++) { for(j=1;j<=c;j++)

{

--精品//初始化第0列 //初始化第0行 //计算第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=c,i=n;i>0;i--) //求装入背包的物品编号 { }

if(V[i][j]>V[i-1][j]) { } else x[i]=0;

x[i]=1; j=j-w[i];

return V[n][c]; } int main() {

int c,n,w[105],v[105],x[105],max;//x[]记录物品的选择情况 cout<<\"请输入背包的重量：\";

cin>>c;

--精品

精品---

cout<<\"请输入物品的个数：\";

cin>>n;

cout<<\"请分别输入物品的重量：\"; }

3、贪心法

for(int i=1;i<=n;i++)

cin>>w[i];

cout<<\"请分别输入物品的价值：\"; for( i=1;i<=n;i++)

cin>>v[i];

max=KnapSack(w,v,x,n,c);

cout<<\"装入背包的物品编号为：\";

for(i=1;i<=n;i++) { }

cout<cout<<\"背包可容纳的最大价值为：\"<if(x[i]==1)

cout<#include

--精品

精品---

#include using namespace std;

//物品结构体 struct _Object {

int Value;//物品价值 int Weight;//物品重量

double AveValue;//物品单位价值 double Num;//物品可以放入的数量 int key;//物品标号 }; //划分

int Partition(_Object r[],int first,int end){

int i=first,j=end; while(iwhile(ir[j].AveValue)

j--;

if(i_Object temp=r[i];

--精品

精品---

}

}

}

r[i]=r[j]; r[j]=temp; i++;

while(ir[j].AveValue)

i++;

if(i_Object temp=r[i]; r[i]=r[j]; r[j]=temp; j--;

return i;

//快速排序

void QuickSort(_Object r[],int first,int end){

int pivot; if(firstpivot=Partition(r,first,end);

--精品

精品---

}

QuickSort(r,first,pivot-1); QuickSort(r,pivot+1,end); }

double knaspsack(int n,int M,_Object object[]) //n为物品个数，M为背包容量 { int i; int C=M;

double maxValue=0;

for(i=0;object[i].Weightobject[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; return maxValue; } int main() {

--精品

精品---

int n,c;

_Object pro[1001]; cout<<\"背包的容量： \"; cin>>c;

cout<<\"请输入物品的个数：\"; cin>>n;

cout<<\"请分别输入物品的重量和价值：\";

for(int i=0;i}

cin>>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);

double maxValue=knaspsack(n,c,pro); cout<<\"背包的可容纳的最大价值为：\"; printf(\"%.2f\ cout<cout<<\"各个物品装入背包的重量分别为：\"; for(k=0;k--精品

精品---

{

for(int j=0;j{

if(pro[j].key==k) //找到原来顺序的物品编号

cout<}

} cout<4、分支限界法

#include #include #include #include #include using namespace std;

//物品结构体 struct obj {

int v;//物品价值 int w;//物品重量

--精品

精品---

double avg;//物品单位价值 int id;//物品编号 };

//节点结构体 struct node {

node *parent,//父亲结点指针 *next;//后继结点指针 int level,//节点所处的层

isin,//记录物品是否装入背包，0代表不装,1代表装入 cw,//当前背包已经装入的物品重量 cv;//当前背包已经装入的物品价值 double ub;//结点的上界值 }; //划分

int Partition(obj r[],int first,int end){

int i=first,j=end; while(iwhile(ir[j].avg)

--精品

精品---

j--;

if(iobj temp=r[i]; r[i]=r[j]; r[j]=temp; i++;

}

while(ir[j].avg)

i++; if(i}

}

return i;

}

//快速排序

--精品

精品---

void QuickSort(obj r[],int first,int end){ } class fzjx{ private:

node *front,//队首指针 *first,//根节点指针 *popv;//解结点指针

double opv;//背包可产生的最大价值 obj *pro;//物品 int n,//物品个数 c;//背包容量 public:

fzjx(obj *pro1,int w1,int n1 ); ~fzjx(); int *flag;

int pivot; if(firstpivot=Partition(r,first,end); QuickSort(r,first,pivot-1); QuickSort(r,pivot+1,end); }

--精品

精品---

double Upb(int i,int cw,int cv);//计算上界值 node *nnoder(node * parent1,int isin1,double ub1); void addnode(node *node1);//将结点添加到队列中 node *nextnode(); //取下一个结点 void fenzjx(); void output(); };

fzjx::fzjx(obj *pro1,int c1,int n1 ) { int i; n=n1;c=c1; pro=new obj [n]; flag=new int[n]; for(i=0;ipro[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=new node[1]; front->next=NULL; opv=0;

popv=new node[1]; popv=NULL; QuickSort(pro,0,n-1); }

fzjx::~fzjx() {

delete[]first; delete[]front; delete[]popv; delete[]pro; }

double fzjx::Upb(int i,int cw,int cv){

int cleft=c-cw; double v=(double)cv; if (iv+=1.0*pro[i].avg*cleft; return v;

--精品

精品---

}

node * fzjx::nnoder(node * parent1,int isin1,double ub1)

{//生成一个新结点

node * node2=new(node); node2->parent=parent1; node2->next=NULL;

node2->level=(parent1->level)+1; node2->isin=isin1; node2->ub=ub1; if(isin1==1) { } else { }

return(node2); }

node2->cw=parent1->cw; node2->cv=parent1->cv;

node2->cw=parent1->cw+pro[parent1->level].w; node2->cv=parent1->cv+pro[parent1->level].v ;

void fzjx::addnode(node *node1)

--精品

精品---

{//将结点加入优先队列 }

node *p=front->next,*next1=front; double ub=node1->ub; while(p!=NULL) { }

if(p==NULL){next1->next=node1; }

if(p->ub{node1->next=p;next1->next=node1;break;}

next1=p; p=p->next;

node * fzjx::nextnode()

{//取上限最大结点 }

node *p=front->next; front->next=p->next; return(p);

void fzjx::fenzjx() {

int i;

--精品

精品---

double ub2; node *node3;

first=new node[1]; //根结点 first->parent=NULL; first->next=NULL; first->level=0; first->cw=0; first->cv=0; first->isin=0; ub2=Upb(0,0,0); first->ub=ub2; front->next=first; while(front->next!=NULL)

{

node3=nextnode(); i=node3->level; if(i==n-1)

{

if(node3->cw+pro[i].w<=c&&(node3->cv+pro[i].v)>opv)

{

opv=node3->cv+pro[i].v; popv=nnoder(node3,1,opv);

--精品

精品---

}

}

if((node3->cv)>opv)

{ }

opv=node3->cv;

popv=nnoder(node3,0,opv);

if(i{

if(node3->cw+pro[i].w<=c&&Upb(i+1,

node3->cw+pro[i].w,node3->cv+pro[i].v)>opv) {

ub2=Upb(i,node3->cw+pro[i].w,node3->cv+pro[i].v);

}

}

}

addnode(nnoder(node3,1,ub2));

ub2=Upb(i,node3->cw,node3->cv); if(ub2>opv)

addnode(nnoder(node3,0,ub2));

--精品

精品---

}

void fzjx::output() {

int i;

for(i=n-1;i>=0;i--)

{ }

flag[pro[i].id]=popv->isin; popv=popv->parent;

cout<<\"装入背包的物品编号为: \"; for(i=0;i{

if(flag[i]==1) cout<}

cout<--精品

cout<<\"背包可以产生的最大价值是: \"<精品---

int c,n;

int i=0; obj *pro1;

cout<<\"请输入背包的容量: \"; cin>>c;

cout<<\"请输入物品的个数: \"; cin>>n;

pro1 = new obj[n];

cout<<\"请分别输入物品的重量和价值:\"; for(i=0;i{

cin>>pro1[i].w>>pro1[i].v; pro1[i].avg=1.0*pro1[i].v/pro1[i].v; pro1[i].id=i; }

fzjx fzjx(pro1,c,n); fzjx.fenzjx(); fzjx.output(); return 0; }

四、运行输出结果：

--精品

精品---

1、蛮力法

用例测试 1：

用例测试 2：

用例测试 1：

2、动态规划法

--精品

精品---

用例测试 2：

用例测试 1： 3、贪心法

--精品

精品---

用例测试 2：

用例测试 1：

4、分支限界法

用例测试 2：

--精品

精品---

五、调试和运行程序过程中产生的问题及采取的措施：

1、问题：蛮力法解决0/1背包问题时，如何表示给定物品集合的所有子集

解决办法：

可以借用“二进制”，将第i个子集的下标i使用二进制表示，对应的二进制各位的数字（0,1）表示相应编号的物品是否包含在该子集中；eg 0101，表示子集{2,4}等等

2、问题：贪心法解决0/1背包问题时，再对物品按照单位价值递减排序后如何记录输入时物品的顺序 解决办法：

可以在表示物品的结构体中增加属性key，在输入时就记录下物品的编号

3、问题：分支界限法解决0/1背包问题时，如何能快速的选取目标函数值

取得极大的结点 解决办法:

可以采用优先级队列的存取结构存放结点，每次都选取队列的队首元素即

--精品

精品---

满足该结点目标函数值取得极大

六、对算法的程序的讨论、分析，改进设想，其它经验教训：

1.在用蛮力法解决0/1背包问题时，为了解决将物品按照单位价值量递减的

顺序排序后，物品在输出时还能保证原来的顺序，虽然通过在输入时就为每个物品添加编号可以解决问题，但同时增大了解决问题的时间开销，只问了匹配物品序号，时间开销就达到Ω（n*n）,这不是解决问题的简单方式，不妨利用分支界限法处理该问题的方式，通过设置一个数组来记录，增大了空间开销，换取了时间上的节约。

2、通过比较蛮力法、动态规划法、贪心法、分支界限法四种方法来解决0/1问题，可以发现，蛮力法设计思想简单，对于输入规模较小时可以快速的得到问题的最优解；当规模增大时，时间开销将达到指数级；同样，动态规划法所需的的时间开销迅速增大，用于存放迭代结果的二维数组V[n][n]的计算时间延长，增大了时间开销；贪心法和分支界限法都涉及要对输入物品的顺序按照单位价值量递减进行排序的问题，采用不同的排序算法会影响算法的执行速度，为了保证物品的顺序不变，不同的策略也会产生不同的效果，分支界限法在最坏情况下等同于蛮力法的时间开销；贪心法只适用于可以全部或部分的装入物品，而对于只限于装入和不装入两种状态，则不能满足问题的要求，但是可以将贪心法用于计算分支界限法的下线，这样就可以更加有效地对解空间进行剪枝，降低时间开销。

--精品