背包问题实验报告

《背包问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《程序设计和算法语言》上机实验报告姓名：刘先俊学号：2014035031班级：信科142题目名称，背包问题一、实验目的：1.掌握动态规划的基本思想2.了解动态规划的背包闷题类型，并能设计相应的算法3.掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法。算法描述(算法设计的思想和实现的步骤，可用文字描述，也可用流程图)：给定N中物品和一个背包。物品i的重量是Wi,其价值位Vi，背包的容量为C。问应该如何选择装入背包的物品，使得转入背包的物品的总价伉为最大？？在选择物品的时候，对每种物品i只有两种选择，即装入背包或不装入背包。不能讲物品i装入多次，也不能只装入物品的一部分。因此，该

2、问题被称为0-1背包问题。问题分析：令V(i,j)表示在前i(l〈=i〈=n)个物品中能够装入容量为就j(l<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数：(1)v(i，o>v(o,j):o(2)V(i,j)=v(i-l,j)j〈WiV(i,j)=max{V(i-l,j)，V(i-1,j-Wi)+Vi)}j>Wi(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背

3、包物品的价值等于第i-1个物品装入容量位j-Wi的背包中的价值加上第i个物品的价值vh(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包屮的最优解。二、源代码：publicclassbb{publicstaticvoidknapsack(int[]int[]w,intc,int[][]m){intn=v.length-1;intjMax=Math.win(w[n]-1,c);for(intj=0;j<=jMax;j++)m[n][j]=0;for(int1=w[n];1<=

4、c;1++)m[n][l]=v[n];for(inti=n-1;i>=1;i--){jMax=Math.wir?(w[i]-l,c);for(intk=0;k<=jMax;k++)m[i][k]=m[i+l][k];for(inth=w[i];h<=c;h++)m[i][h]=Math.znox(m[i+1][h],m[i+l][h-w[i]]+v[i]);}m[0][c]=m[l][c];if(c>=w[0])m[0][c]=Math./wax(m[0][c],m[l][c-w[0]]+v[0]);System.out.printIn(Hbestw=M+m[0][c]);}publi

5、cstaticvoidtraceback(int[][]int[]w,intc,int[]x)intn=w.length-1;for(inti=0;i0)?l:0;}publicstaticvoidmain(String[]args){int[]ww={2,2,6j5j4};int[]vv={6,3,5,4,6};int[][]mm=newint[ll][11];knopsack^MM10,mm)jint[]xx=newint[ww.length

6、];traceback(mm^vi^10，xx);for(inti=0;i