


全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验3. 基于动态规划方法求解0-1背包问题实验内容本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试),在针对0-1背包问题求解的实践中理解动态规划 (Dynamic Programming, DP) 方法的思想、求解策略及步骤。作为挑战:可以考虑基于跳跃点的改进算法,以及对连续型物品重量/背包容量的支持。实验目的u 理解动态规划方法的核心思想以及动态规划方法的求解过程;u 从算法分析与设计的角度,对0-1背包问题的基于DP法求解有更进一步的理解。环境要求对于环境没有特别要求。对于算法实现,可以自由选择C, C+, Java,甚至于其他程序设计语言。实验步骤步骤1:理解问题,给出问题的描述。步骤2:算法设计,包括策略与数据结构的选择步骤3:描述算法。希望采用源代码以外的形式,如伪代码或流程图等;步骤4:算法的正确性证明。需要这个环节,在理解的基础上对算法的正确性给予证明;步骤5:算法复杂性分析,包括时间复杂性和空间复杂性;步骤6:算法实现与测试。附上代码或以附件的形式提交,同时贴上算法运行结果截图;步骤7:技术上、分析过程中等各种心得体会与备忘,需要言之有物。说明:步骤1-6在“实验结果”一节中描述,步骤7在“实验总结”一节中描述。实验结果步骤1:理解问题给定n和物品和一人背包,物品i的重量是wi,其价值为vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?举例:若商店一共有5类商品,重量分别为:3,4,7,8,9价值分别为:4,5,10,11,13则:所选商品的最大价值为24所选商品的一个序列为:0001 1步骤2:算法设计动态规划算法与分治法类似,其基本思想是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的,若用分治法解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。步骤3:描述算法1)编写voidValue(Typep,Typew,Typec,Typen,TypefnMaxnMax)函数,用以计算各个最优子序列的值;2)编写voidcompute(TypefnMaxnMax,Typew,Typep,Typec,Typen,Typex)函数用以确定计算装入的物品x和装入的物品的总重量totalWeight;3)编写主函数,控制输入输出;4)改进和检验程序。步骤4:算法的正确性证明设(y1,y2,yn)是 (3.4.1)的一个最优解.则(y2,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,zn)是上述子问题的一个最优解,而(y2,y3,yn)不是它的最优解。显然有 vizi viyi (i=2,n) 且 w1y1+ wizi viyi, (i=1,n) 说明(y1,z2, z3,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,yn)不是背包问题的最优解,矛盾。步骤5:算法复杂性分析;假设Si的序偶是|i|。在i的情况下,每个i由1i-1和1i归并而成,并且1i|=|i-1|,因此i|=2|i-1|。在最坏情况下没有序偶被清除,所以对|i|求和(i=0,1,2,n-1)的结果是n-1,也就是说的空间复杂度为(n)。由i-1生成i需要|i-1|的时间,所以在计算S0,S1,S2,Sn-1时所消耗的总时间为(|i-1|),0in。由于in,所以计算这些i总的时间为(n)。该算法的时间复杂性为(n),似乎表明当很大时它的有效性不会让人满意,但由于支配规则的引入,很好的清除了不满足约束的序偶,因而该算法在很多情况下都能在可接受的时间内求出决策序列。步骤6:算法实现与测试;实验总结
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年监理工程师理论与法规试题解析高频考点攻略
- 护理管理制度培训体系构建
- 公务员考试行测图形推理2025年专项冲刺训练试卷
- 肥胖病人的麻醉管理
- 2025年考研中国文学史古代文学模拟试题全解析
- 阿米巴管理培训
- 2025年注册消防工程师技术实务消防设施卷实战案例分析试题集
- 关注食品安全 共建和谐校园-学校饮食安全班会
- MySQL数据流处理技术试题及答案
- 备战2024年高考数学一轮复习(一隅三反基础版新高考专用)2-1 不等式的性质及一元二次不等式(精讲)(基础版)(解析版)
- 安徽省皖南八校2025届高三下学期第三次联考物理试卷 含解析
- 安徽省部分高中2025届高考生物四模试卷含解析
- 2025-2030全球及中国燃气轮机服务行业市场现状供需分析及市场深度研究发展前景及规划可行性分析研究报告
- 2025-2030中国老年教育行业发展前景及发展策略与投资风险研究报告
- 初中学生安全教育课件
- 2025年下半年度云南云勤服务集团限责任公司高校毕业生公开招聘13人易考易错模拟试题(共500题)试卷后附参考答案
- 2024年延安通和电业有限责任公司招聘考试真题
- 2024年新人教版英语三年级上册 U6 A learn 教学课件
- 辽宁省点石联考2025届高三下学期5月联合考试 地理 含答案
- 项目平行分包协议书范本
- 茶廉文化课件
评论
0/150
提交评论