算法背包问题

海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师实验题目：背包问题实验目的：掌握动态规划、贪心算法的原理，并能够按其原理编程实现解决背包问题，以加深对上述方法的理解。实验内容：一个旅行者准备随身携带一个背包.可以放入背包的物品有n种,每种物品的重量和价值分别为wj,vj.如果背包的最大重量限制是b,怎样选择放入背包的物品以使得背包的价值最大?目标函数：约束条件：线性规划问题由线性条件约束的线性函数取最大或最小的问题整数规划问题线性规划问题的变量xj都是非负整数Fk(y)：装前k种物品,总重不超过y,背包的最大价值i(k,y)：装前k种物品,总重不超过y,背包达最大价值时装入物品的最大标号递推方程、边界条件、标记函数实例计算：v1=1,v2=3,v3=5,v4=9,w1=2,w2=3,w3=4,w4=7,b=10Fk(y)的计算表如下:K/y1234567891010112233445201334667993013556810101140135569101012N,max11jnjjjnjjjxbxwxv0)()(0,0)0(,0,0)(})(),(max{)(11101yyFvwyyFnkFbyyFvwyFyFyFkkkkkkk海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师实验步骤：1、分析题目；2、打开NetBeans软件，新建一个名叫Knapsackdxj的项目，并对其进行保存；3在新建的项目下对我们所分析的题目进行编写；4、调试所编写的程序；5、运行文件，并对其进行测试，看是否正确。实验结果：海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师实验小结：在做本次实验之前，自己对动态规划、贪心算法的原理不是非常的理解，花了很多时间看了课本上的相关内容。当你懂得算法的基本原理后，再参考老师所提供的代码进行完善补充，必须结合算法的实际情况对代码中的相关变量进行修改，这样才能充分利用课本所提供的代码完成本次实验。通过本次试验，自己基本上掌握上述算法解背包问题的原理，达到实验的目的。实验代码：Knapsack.Javapackagechap4;importjava.util.Scanner;/****@authorJinyu*/publicclassKnapsack{//***********************常量定义*****************************staticfinalintMAX_NUM=20;staticfinalintMAX_WEIGHT=100;//*********************自定义数据结构*************************//********************题目描述中的变量************************privatefinalintweight[]=newint[MAX_NUM];privatefinalintvalue[]=newint[MAX_NUM];privatefinalintx[]=newint[MAX_NUM];privatefinalintm[][]=newint[MAX_NUM][MAX_NUM];海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师privatefinalints[][]=newint[MAX_NUM][MAX_NUM];privateintn;privateintw;inth;intl;//***********************算法实现*****************************publicvoidsolve(){intk=1;inta=1;for(inti=1;i=n;i++){for(intj=1;j=w;j++){a=1;k=1;if(weight[i]=j){h=weight[i];l=value[i];while(h=j&&a==1){//判断是否能够装入h=weight[i]*k;//k是放入物品的次数，每放一次，k加1再重新判断是否还能放进l=value[i]*k;//System.out.println(h+d);if(m[i-1][j]m[i-1][j-h]+l||m[i][j](m[i-1][j-h]+l)){//判断是否应该装入if(k==1){//第一次的时候才执行不放入的操作，k不等于1的时候保持上一次操作的结果不进行改变海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师m[i][j]=m[i-1][j];//不装入s[i][j]=0;}a=0;}else{m[i][j]=m[i-1][j-h]+l;//应该装入s[i][j]=k;//存放装入次数，用于求最优解k++;//装入后k加1h=weight[i]*k;l=value[i]*k;//System.out.println(h+e);//测试}//System.out.println(h+c);//System.out.println(i++j++m[i][j]);//测试}}elseif(m[i][j]m[i-1][j]){//无法装入m[i][j]=m[i-1][j];if(k==1){s[i][j]=0;}}//System.out.println(i++j++m[i][j]);//测试}}System.out.println(可装入物品的最大价值为：+m[n][w]);//for(inti=1;i=n;i++){//测试//for(intj=1;j=w;j++){海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师//System.out.println(i++j++s[i][j]);//}//}}publicvoidtrance(){inty=w;intj=n;x[j]=s[j][y];//获取最后一样物品的装入信息for(inti=j;i1;i--){//由最后一个数据向上推算y=y-x[i]*weight[i];x[i-1]=s[i-1][y];//将每个物品的装入信息存放起来}for(inti=1;i=n;i++){System.out.println(第+i+个物品放入+x[i]+样);}}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++){海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21学号：20132821320066成绩教师weight[i]=scanner.nextInt();value[i]=scanner.nextInt();}}}Test.javapackagechap4;/****@authorJinyu*/publicclassTest{/***@paramargsthecommandlinearguments*/publicstaticvoidmain(String[]args){//MatrixChainAppapp1=newMatrixChainApp();//app1.test();Knapsackapp=newKnapsack();app.input();app.solve();app.trance();}}