资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
海南大学学生实验报告课程名称:算法实验 班级: 物联2班 姓名: 蒋煜辉 日期 15.11.21 实验题目:背包问题实验目的:掌握动态规划、贪心算法的原理,并能够按其原理编程实现解决背包问题,以加深对上述方法的理解。实验内容:一个旅行者准备随身携带一个背包. 可以放入背包的物品有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 = 10 Fk(y) 的计算表如下:K/y1234567891010112233445201334667993013556810101140135569101012实验步骤: 1、分析题目; 2、打开NetBeans软件,新建一个名叫 Knapsackdxj的项目,并对其进行保存; 3在新建的项目下对我们所分析的题目进行编写; 4、调试所编写的程序; 5、运行文件,并对其进行测试,看是否正确。实验结果:实验小结:在做本次实验之前,自己对动态规划、贪心算法的原理不是非常的理解,花了很多时间看了课本上的相关内容。当你懂得算法的基本原理后,再参考老师所提供的代码进行完善补充,必须结合算法的实际情况对代码中的相关变量进行修改,这样才能充分利用课本所提供的代码完成本次实验。通过本次试验,自己基本上掌握上述算法解背包问题的原理,达到实验的目的。实验代码:Knapsack.Javapackage chap4;import java.util.Scanner;/* * * author Jinyu */public class Knapsack /*常量定义* static final int MAX_NUM = 20; static final int MAX_WEIGHT = 100;/*自定义数据结构* /*题目描述中的变量* private final int weight = new intMAX_NUM; private final int value = new intMAX_NUM; private final int x = new intMAX_NUM; private final int m = new intMAX_NUMMAX_NUM; private final int s = new intMAX_NUMMAX_NUM; private int n; private int w; int h; int l;/*算法实现* public void solve() int k = 1; int a = 1; for (int i = 1; i = n; i+) for (int j = 1; j = w; j+) a = 1; k = 1; if (weighti = j) h = weighti; l = valuei; while (h mi - 1j - h + l | mij (mi - 1j - h + l) /判断是否应该装入 if (k = 1) /第一次的时候才执行不放入的操作,k不等于1的时候保持上一次操作的结果不进行改变 mij = mi - 1j;/不装入 sij = 0; a = 0; else mij = mi - 1j - h + l;/应该装入 sij = k;/存放装入次数,用于求最优解 k+;/装入后k加1 h = weighti * k; l = valuei * k;/ System.out.println(h + e);/测试 / System.out.println(h + c);/ System.out.println(i + + j + + mij);/测试 else if (mij mi - 1j) /无法装入 mij = mi - 1j; if (k = 1) sij = 0; / System.out.println(i + + j + + mij);/测试 System.out.println(可装入物品的最大价值为: + mnw);/ for (int i = 1; i = n; i+) /测试/ for (int j = 1; j 1; i-) /由最后一个数据向上推算 y = y - xi * weighti; xi - 1 = si - 1y;/将每个物品的装入信息存放起来 for (int i = 1; i = n; i+) System.out.println(第 + i + 个物品放入 + xi + 样); public void input() Scanner scanner = new Scanner(System.in); System.out.println(请输入背包能够承受的总重量:); w = scanner.nextInt(); System.out.println(请输入可以装入背包的物品的种类:); n = scanner.nextInt(); System.out.println(请输入 + n + 种物品中每一种物品的重量和价值:); for (int i = 1; i = n; i+) weighti = scanner.nextInt(); valuei = scanner.nextInt(); Test.javapackage chap4;/* * * author Jinyu */public class Test /* * param args the command line arguments */
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号