算法设计与分析实验报告背包问题.docx

算法设计与分析实验报告背包问题.docx

《算法设计与分析实验报告背包问题.docx》由会员分享，可在线阅读，更多相关《算法设计与分析实验报告背包问题.docx（6页珍藏版）》请在冰点文库上搜索。

算法设计与分析

实验报告

—0/1背包问题

-

【问题描述】

给定n种物品和一个背包。

物品i的重量是，其价值为，背包容量为C。

问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？

【问题分析】

0/1背包问题的可形式化描述为：

给定C>0,>0,>0,，要求找出n元0/1向量，使得，而且达到最大。

因此0/1背包问题是一个特殊的整数规划问题。

【算法设计】

设0/1背包问题的最优值为m（i,j），即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。

由0/1背包问题的最优子结构性质，可以建立计算m（i,j）的递归式如下：

max{m（i+1,j）,m（i+1,j-）+}

m（i,j）=

m（i+1,j）

m（n,j）=

0

【算法实现】

#include

#include

#include

intmin（intw,intc）

{

inttemp;

if（w

else

temp=c;

returntemp;

}

Intmax（intw,intc）

{

inttemp;

if（w>c） temp=w;

else

temp=c;

returntemp;

}

voidknapsack（intv[],intw[],int**m,intc,intn） //求最优值

{

intjmax=min（w[n]-1,c）;

for（intj=0;j<=jmax;j++）

m[n][j]=0;

for（intjj=w[n];jj<=c;jj++）

m[n][jj]=v[n];

for（inti=n-1;i>1;i--） //递归部分

{

jmax=min（w[i]-1,c）;

for（intj=0;j<=jmax;j++）

m[i][j]=m[i+1][j];

for（intjj=w[i];jj<=c;jj++）

m[i][jj]=max（m[i+1][jj],m[i+1][jj-w[i]]+v[i]）;

}

m[1][c]=m[2][c];

if（c>=w[1]）

m[1][c]=max（m[1][c],m[2][c-w[1]]+v[1]）;

cout<

"<

cout<

cout<<"&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&"<

}

inttraceback（intx[],intw[],int**m,intc,intn）//回代，求最优解

{

out<

"<

for（inti=1;i

{

if（m[i][c]==m[i+1][c]） x[i]=0;

else

{

x[i]=1;

c-=w[i];

}

}

x[n]=（m[n][c]）?

1:

0;

for（inty=1;y<=n;y++）

cout<

cout<

returnx[n];

}

voidmain（）

{

int n,c;

int**m;

cout<<"&&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&"<

cout<<"请输入物品个数:

";

cin>>n;

cout<

";

cin>>c;

int*v=newint[n+1];

cout<

"<

for（inti=1;i<=n;i++）

cin>>v[i];

int*w=newint[n+1];

cout<

"<

for（intj=1;j<=n;j++）

cin>>w[j];

int*x=newint[n+1];

m=newint*[n+1]; //动态的分配二维数组

for（intp=0;p

m[p]=newint[c+1];

knapsack（v,w,m,c,n）;

traceback（x,w,m,c,n）;

}

【运行结果】