算法背包问题.doc
《算法背包问题.doc》由会员分享,可在线阅读,更多相关《算法背包问题.doc(6页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、实验题目:背包问题实验目的:掌握动态规划、贪心算法的原理,并能够按其原理编程实现解决背包问题,以加深对上述方法的理解。实验内容:一个旅行者准备随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量与价值分别为 wj , vj . 如果背包的最大重量限制是 b, 怎样选择放入背包的物品以使得背包的价值最大目标函数:约束条件:线性规划问题 由线性条件约束的线性函数取最大或最小的问题整数规划问题 线性规划问题的变量 xj 都是非负整数Fk(y):装前 k 种物品, 总重不超过 y, 背包的最大价值i(k,y):装前 k 种物品, 总重不超过 y, 背包达最大价值时装入物品的最大标号递推方程
2、、边界条件、标记函数实例计算: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、运行文件,并对其进展测试,看是否正确。实验结果:实验小结:在做本次实验之前,自己
3、对动态规划、贪心算法的原理不是非常的理解,花了很多时间看了课本上的相关内容。当你懂得算法的根本原理后,再参考教师所提供的代码进展完善补充,必须结合算法的实际情况对代码中的相关变量进展修改,这样才能充分利用课本所提供的代码完本钱次实验。通过本次试验,自己根本上掌握上述算法解背包问题的原理,到达实验的目的。实验代码:Knapsack.Javapackage chap4;import java.util.Scanner; * author Jinyupublic class Knapsack /*常量定义* static final int MAX_NUM = 20; static final in
4、t 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;/*
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 背包 问题
限制150内