完全背包问题

海南大学学生实验报告课程名称:班级：姓名：日期学号：成绩教师实验题目：完全背包问题实验目的：1、学习掌握动态规划算法2、学习划分子问题及确定优化函数并掌握其思想实验内容：一个旅行者准备随身携带一个背包.可以放入背包的物品有n种,每种物品的重量和价值分别为wj,vj.如果背包的最大重量限制是b,怎样选择放入背包的物品以使得背包的价值最大?实验步骤：1、由线性条件约束的线性函数取最大或最小的问题2、Fk(y)：装前k种物品,总重不超过y,背包的最大价值3、ik(y)：装前k种物品,总重不超过y,背包达最大价值时装入物品的最大标号4、确定递推方程、边界条件、标记函数实验结果：海南大学学生实验报告课程名称:班级：姓名：日期学号：成绩教师实验代码：packagepacksack;importjava.util.Scanner;publicclassProject{staticfinalintMAX_NUM=20;staticfinalintMAX_WEIGHT=100;privatefinalintweight[]=newint[MAX_NUM];privatefinalintvalue[]=newint[MAX_NUM];privatefinalintx[]=newint[MAX_NUM];privatefinalintm[][]=newint[MAX_NUM][MAX_NUM];privatefinalints[][]=newint[MAX_NUM][MAX_NUM];privateintn;privateintw;publicvoidsolve(){for(inti=1;i=n;i++){for(intj=1;j=w;j++){if(weight[i]=j){if(m[i-1][j]m[i][j-weight[i]]+value[i]){m[i][j]=m[i-1][j];s[i][j]=s[i-1][j];}else{m[i][j]=m[i][j-weight[i]]+value[i];s[i][j]=i;}}else{m[i][j]=m[i-1][j];s[i][j]=s[i-1][j];}}}System.out.println(可装入物品的最大价值为：+m[n][w]);}publicvoidtrackSolution(){inty=w;intj=n;while(y!=0){j=s[j][y];海南大学学生实验报告课程名称:班级：姓名：日期学号：成绩教师x[j]=1;y=y-weight[j];while(s[j][y]==j){y=y-weight[j];x[j]++;}}System.out.print(最佳装入方案：{);for(inti=1;i=n;i++){System.out.print(x[i]);if(i!=n){System.out.print(,);}}System.out.println(});}publicvoidinput(){Scannerscanner=newScanner(System.in);System.out.println(请输入背包能够承受的总重量：);w=scanner.nextInt();System.out.println(请输入可以装入背包的物品的种类：);n=scanner.nextInt();System.out.println(请输入+n+种物品中每一种物品的价值：);for(inti=1;i=n;i++){value[i]=scanner.nextInt();}System.out.println(请输入+n+种物品中每一种物品的重量：);for(inti=1;i=n;i++){weight[i]=scanner.nextInt();}}}packagepacksack;publicclassTest{publicstaticvoidmain(String[]args){Projectapp=newProject();app.input();app.solve();app.trackSolution();}}