下载本文档
版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
1、实验报告：动态规划-0-1背包问题)范文 xxxx 大 学 计 算 机 学 院 实 验 报 告 计算机学院 2021 级 软件工程 专业 5 班 指导教师 学号 姓名 2021 年 10 月 21 日 成绩 课程名称 算法分析与设计 实验名称 动态规划 -0-1 背包问题理解递归算法的概念 实验目的 通过模仿 0-1 背包问题，了解算法的思想练习 0-1 背包问题算法 实验仪器 电脑、 jdk 、 eclipse 和器材 实验： 0-1 背包算法：给定 n 种物品，每种物品都有对应的重量 weight 和价值 value ，一个容 量为 maxweight 的背包，问：应该如何选择装入背包的物
2、品，使得装入背包的物品的总价值 最大。（面对每个物品，我们只有拿或者不拿两种选择，不能选择装入物品的某一部分，也 实 验 不能把同一个物品装入多次）代码如下所示： 内 public class knapsackproblem 容 /* 、 上 * paramweight 物品重量 机 * paramvalue 物品价值 调 * parammaxweight 背包最大重量 试 程 * return maxvalueij 中， i 表示的是前 i 个物品数量， j 表示的是重量 序 */ 、 public static int knapsack( int weight , int value ,
3、int maxweight ) 程 序 运 行 结 果 实 验 内 int n = ; 包问题的算法思想：将前 i 个物品放入容量 容 为 w 的背包中的最大价值。有如下两种情况： 、 若当前物品的重量小于当前可放入的重量，便可考虑是 上 否要将本件物品放入背包中或者将背包中的某些物品拿出 机 来再将当前物品放进去；放进去前需要比较（不放这个物 调 品的价值）和（这个物品的价值放进去加上当前能放的总 试 重量减去当前物品重量时取 i-1 个物品是的对应重量时候 程 的最高价值），如果超过之前的价值，可以直接放进去，反 序 之不放。 、 若当前物品的重量大于当前可放入的重量，则不放入 程 背包问题利用动态规划的思路可以这样理解：阶段是"物 序 品的件数'，状态就是"背包剩下的容量' ，fi,v 表示设 运 从前 i 件物品中选择放入容量为 v 的背包的最大价值。那 行 么状态转移的方法为 : 结 fiv=maxfi-1v,fi-1v-wi+ci 果 这个方程可以理解为：只考虑子问题"将前 i 个物品放入 容量为 v 的背包中的最大价值' 那么可以考虑不放入 i ，最 大价值就和 i 无关，就是 fi-1v, 如果放入第 i 个物品， 价值就是 f
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论