0-1背包问题实验报告.docx

0-1背包问题实验报告
小组成员:
姓名班级学号
贾倩楠 2010211307 10211339
骆亮亮 2010211307 10211318
高婧 2010211308 10211370
:
0-1背包问题

问题描述:
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装入背包中物品的总价值最大?
在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包。不能将物品装入背包多次,也不能只装入部分的物品。0-1背包问题是一个特殊的整数规划问题

,设计解决上述问题的算法,找出最大背包价值的装法。
。
:
问题求解思路
-1背包问题的最优子结构性质,建立计算m[i][j]的递归式如下:
:
从数组的最右下角开始寻找,如若m[i][weight] != m[i-1][weight],则该第i个物品就在背包中,将其从最大价值量中去掉,然后再接着寻找下一个在背包中的物品,直至i=0。
关键数据结构:
一个二维数组,两个一维数组,两个整型变量
int m[N+1][M+1]={0};//用于存储当前最好的价值量
int number,weight;//number表示物品的种类,weight表示背包重量的最大值
int w[N]={0},v[N]={0};//分别表示物品的重量和价值
函数模块:
Main函数调用其余两个个函数完成算法:
void knapsack(int number,int weight,int * w,int * v,int m[][M+1]);//整理背包函数,找出最大价值
void findobject(int number,int weight,int * w,int * v,int m[][M+1]);//找出所有在背包里的物品的函数
:
算法:
1. void knapsack(int number,int weight,int * w,int * v,int m[][M+1])
{//数组m[][],其横坐标row表示物品是第几个,纵坐标col表示当前背包中物品的重量从1到weight
int row,col;
for(row=1;row<=number;row++)
for(col=1;col<=weight;col++)
{
if(col >= w[row])//当背包重量大于第row个物品的重量时,再继续进行判断
{
if(m[row-1][col-w[row]] + v[row] > m[row-1][col])
m[row][col] = m[row-1][col-w[row]] + v[row];
else
m[row][col] = m[row-1][col];//判断加入该第row个物品是否会增大价值量,若增大则加入,否则不加
}
else
m[row][col] = m[row-1][col];//如果背包重量小于w[row],则不加入任何物品,价值量不变
}
printf("The most value of the knapsack is:%d.\n",m[number][weight]);//输出最大价值量
}
2. void findobject(int number,int weight,int * w,int * v,int m[][M+1])
{
int i;
int x[N]={0};
for(i=number;i>0;i--)//从数组的最右下角开始找寻,直到找到最开始的m[0][]
{
if(m[i][weight] != m[i-1][weight])
{
x[i] = 1;
weight = weight - w[i];//将找到的第i个物品从背包的重量中去掉
printf("%dth object is chosen. weight:%d,value:%d\n",i,w[i],v[i]);//输出找到的物品的信息
}
}
}
:
当输入的数据不符合要求时:
:(n为物品总数,c为重量限制背包容量)
从m(i,j)的递归式容易看出,算法需要O(nc)计算时间。当背包容量c很大时,算法需要的计算时间较多。例如,当c>2n时,算法需要Ω(n2n)计算时间
:
算法思路:
(i,j)的递归式容易证明,