资源描述：
《算法背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21实验题目：背包问题实验目的：掌握动态规划、贪心算法的原理，并能够按其原理编程实现解决背包问题，以加深对上述方法的理解。实验内容：一个旅行者准备随身携带一个背包.可以放入背包的物品有n种,每种物品的重量和价值分别为wj,vj.如果背包的最大重量限制是b,怎样选择放入背包的物品以使得背包的价值最大?目标函数：约束条件：线性规划问题由线性条件约束的线性函数取最大或最小的问题整数规划问题线性规划问题的变量xj都是非负整数Fk(y)：装前k种物品,总重不超过y,背包的最大价值i(k,y)：装前k种物品,总
2、重不超过y,背包达最大价值时装入物品的最大标号递推方程、边界条件、标记函数实例计算：v1=1,v2=3,v3=5,v4=9,w1=2,w2=3,w3=4,w4=7,b=10Fk(y)的计算表如下:K/y1234567891010112233445201334667993013556810101140135569101012学号：20132821320066成绩教师海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21实验步骤：1、分析题目；2、打开NetBeans软件，新建一个名叫Knapsackdxj的项目，并对其进行保存；3在新建的项目下对我们
3、所分析的题目进行编写；4、调试所编写的程序；5、运行文件，并对其进行测试，看是否正确。实验结果：学号：20132821320066成绩教师海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21实验小结：在做本次实验之前，自己对动态规划、贪心算法的原理不是非常的理解，花了很多时间看了课本上的相关内容。当你懂得算法的基本原理后，再参考老师所提供的代码进行完善补充，必须结合算法的实际情况对代码中的相关变量进行修改，这样才能充分利用课本所提供的代码完成本次实验。通过本次试验，自己基本上掌握上述算法解背包问题的原理，达到实验的目的。实验代码：Knapsack
4、.Javapackagechap4;importjava.util.Scanner;/****@authorJinyu*/publicclassKnapsack{//***********************常量定义*****************************staticfinalintMAX_NUM=20;staticfinalintMAX_WEIGHT=100;//*********************自定义数据结构*************************//********************题目描述中的变量**************
5、**********privatefinalintweight[]=newint[MAX_NUM];privatefinalintvalue[]=newint[MAX_NUM];privatefinalintx[]=newint[MAX_NUM];privatefinalintm[][]=newint[MAX_NUM][MAX_NUM];学号：20132821320066成绩教师海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21privatefinalints[][]=newint[MAX_NUM][MAX_NUM];privateintn;p
6、rivateintw;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;//Sys
7、tem.out.println(h+"d");if(m[i-1][j]>m[i-1][j-h]+l
8、
9、m[i][j]>(m[i-1][j-h]+l)){//判断是否应该装入if(k==1){//第一次的时候才执行不放入的操作，k不等于1的时候保持上一次操作的结果不进行改变学号：20132821320066成绩教师海南大学学生实验报告课程名称:算法实验班级：物联2班姓名：蒋煜辉日期15.11.21m[i][j]=m[i-1][j];//不装入s[i][j]=0;}a=0;}else{m[i][
