完全背包问题.doc

《完全背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验题目：完全背包问题实验目的：1、学习掌握动态规划算法2、学习划分子问题及确定优化函数并掌握其思想实验内容：一个旅行者准备随身携带一个背包.可以放入背包的物品有n种,每种物品的重量和价值分别为wj,vj.如果背包的最大重量限制是b,怎样选择放入背包的物品以使得背包的价值最大?实验步骤：1、由线性条件约束的线性函数取最大或最小的问题2、Fk(y)：装前k种物品,总重不超过y,背包的最大价值3、ik(y)：装前k种物品,总重不超过y,背包达最大价值时装入物品的最大标号4、确定递推方程、边界条件、标记函数实验结果：实验代码：packagepacksack;importjava.ut

2、il.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];pr

3、ivateintn;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(

4、"可装入物品的最大价值为："+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("}");}publicvoidin

5、put(){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+"种物品中每一种物品的重量

6、：");for(inti=1;i<=n;i++){weight[i]=scanner.nextInt();}}}packagepacksack;publicclassTest{publicstaticvoidmain(String[]args){Projectapp=newProject();app.input();app.solve();app.trackSolution();}}