实验报告：动态规划_第1页
实验报告：动态规划_第2页
实验报告：动态规划_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、XXXX大学计算机学院实验报告计算机学院2017 级软件工程专业班指导教师学号 姓名2019年10月21日 成绩课程名称算法分析与设计实验名称动态规划一-0-1背包问题实验目的理解递归算法的概念通过模仿0-1背包问题，了解算法的思想练习0-1背包问题算法实验仪器 和器材电脑、jdk、eclipse实 验 内 容、 上 机 调 试 程序、 程 序 运 彳亍 结果实验：0-1背包算法：给定N种物品，每种物品都有对应的重量weight和价值value,-个容 量为maxWeight的背包，问：应该如何选择装入背包的物品，使得装入背包的物品的总价值 最大。(面对每个物品，我们只有拿或者不拿两种选择，不

2、能选择装入物品的某一部分，也 不能把同一个物品装入多次)代码如下所示：public class KnapsackProblem /*param weight 物品重量param value 物品价值param maxweight背包最大重量* return maxvalueij中，i表示的是前i个物品数量，j表示的是重量*/public static int knapsack(int weight, int value, int maxweight)l-wl me nu_5 e-a rclhjp42 43 4447 48g5254 15 51- pQ59 巨仞61 !62 65 &4JrIJ

3、I Kh-b p s-a ck Prolb- le m Ja va 阳;昆尽V苯南遂*赫克的俏值)和:摩个物品的仿值放进去 KnapsackPrab-le-m Java Applicatan C:Pfdgram File-sJavajre-1 .S.D_1 51 者桓王里为s是时，背包的取大的伯廿直是:： 11mt n 一包问题的算法思想：将前i个物品放入容量 int n ,为w的背包中的最大价值。有如下两种情况： 若当前物品的重量小于当前可放入的重量，便可考虑是 否要将本件物品放入背包中或者将背包中的某些物品拿出 来再将当前物品放进去；放进去前需要比较（不放这个物 品的价值）和（这个物品的价值放进去加上当前能放的总 重量减去当前物品重量时取i-1个物品是的对应重量时候 的最高价值），如果超过之前的价值，可以直接放进去，反 之不放。若当前物品的重量大于当前可放入的重量，则不放入 背包问题利用动态规划的思路可以这样理解：阶段是“物 品的件数”，状态就是“背包剩下的容量”，fi,v表示设 从前i件物品中选择放入容量为V的背包的最大价值。那 么状态转移的方法为:fiv=maxfi-1v,fi-1v-wi+ci这个方程可以理解为：只考虑子问题“将前i个物品放入容量为v的背包中的最大价值”那么可以考虑不放入i，最 大价值就和i无关，就是fi-1v,如果放入第

人人文库> 全部分类> 图纸下载 > 毕业设计

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论