背包问题实验报告.doc

《程序设计和算法语言》上机实验报告
姓名: 刘先俊学号: 2014035031 班级: 信科142
题目名称: 背包问题
实验目的:
1. 掌握动态规划的基本思想 
2. 了解动态规划的背包问题类型,并能设计相应的算法 
3. 掌握动态规划算法时间空间复杂度分析,以及问题复杂性分析方法。
算法描述(算法设计的思想和实现的步骤,可用文字描述,也可用流程图):
给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi ,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大??
在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能讲物品i装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。 
 
问题分析:令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值,则可以得到如下的动态规划函数:
(1)   V(i,0)=V(0,j)=0 
(2)   V(i,j)=V(i-1,j)  j<wi       V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi
(1)式表明:如果第i个物品的重量大于背包的容量,则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的,即物品i不能装入背包;第(2)个式子表明:如果第i个物品的重量小于背包的容量,则会有一下两种情况:(a)如果把第i个物品装入背包,则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包,则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然,取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。 
源代码:
public class bb
{
public static void knapsack(int[] v, int[] w, int c, int[][] m)
{
int n = -1;
int jMax = (w[n]-1, c);
for(int j = 0; j <= jMax; j++)
m[n][j] = 0;
for (int l = w[n]; l <= c; l++)
m[n][l] = v[n];
for(int i = n-1; i >=1; i--)
{
jMax = (w[i]-1,c);
for(int k = 0; k <=jMax; k++)
m[i][k] = m[i+1][k];

for(int h = w[i]; h <= c; h++)
m[i][h] = (m[i+1][h],m[i+1][h-w[i]]+v[i]);
}
m[0][c] = m[1][c];
if(c >= w[0])
m[0][c] = (m[0][c],m[1][c-w[0]]+v[0]);
("