【精编】实验报告:动态规划---0-1背包问题).pdf

上传人:索**** 文档编号:83451451 上传时间:2023-03-30 格式:PDF 页数:4 大小:117.14KB
返回 下载 相关 举报
【精编】实验报告:动态规划---0-1背包问题).pdf_第1页
第1页 / 共4页
【精编】实验报告:动态规划---0-1背包问题).pdf_第2页
第2页 / 共4页
点击查看更多>>
资源描述

《【精编】实验报告:动态规划---0-1背包问题).pdf》由会员分享,可在线阅读,更多相关《【精编】实验报告:动态规划---0-1背包问题).pdf(4页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、拿或者不拿两种选择,不能选择装入物品的某一部分,也不能把同一个物品装入多次)代码如下所示:publicclass KnapsackProblem/*param weight 物品重量*param value 物品价值*param maxweight 背包最大重量*return maxvalueij中,i 表示的是前 i 个物品数量,j 表示的是重量*/publicstaticint knapsack(int weight,int value,intmaxweight)intn=;包问题的算法思想:将前 i 个物品放入容量为 w的背包中的最大价值。有如下两种情况:若当前物品的重量小于当前可放入的

3、重量,便可考虑是否要将本件物品放入背包中或者将背包中的某些物品拿出来再将当前物品放进去;放进去前需要比较(不放这个物品的价值)和(这个物品的价值放进去加上当前能放的总重量减去当前物品重量时取i-1 个物品是的对应重量时候的最高价值),如果超过之前的价值,可以直接放进去,反之不放。若当前物品的重量大于当前可放入的重量,则不放入背包问题利用动态规划的思路可以这样理解:阶段是“物品的件数”,状态就是“背包剩下的容量”,fi,v表3 容、上机调试程序、程序运行结果实示设从前 i 件物品中选择放入容量为V的背包的最大价值。那么状态转移的方法为:fiv=maxfi-1v,fi-1v-wi+ci这个方程可以理解为:只考虑子问题“将前i 个物品放入容量为 v的背包中的最大价值”那么可以考虑不放入i,最大价值就和 i 无关,就是 fi-1v,如果放入第 i 个物品,价值就是 fi-1v-wi+valuei,只取最大值即可。4 验内容、上机调试程序、程序运行结果

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 高考资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁