实验3.基于动态规划方法求解01背包问题.docx

实验3.基于动态规划方法求解01背包问题.docx精品文档
精品文档
1
精品文档
精品文档 你我共享
0-1背包问题
实验内容
本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法
描述、算法正确性证明、算精品文档
精品文档
1
精品文档
精品文档 你我共享
0-1背包问题
实验内容
本实验要求基于算法设计与分析的一般过程（即待求解问题的描述、算法设计、算法
描述、算法正确性证明、算法分析、算法实现与测试） ，在针对 0-1背包问题求解的实践中
理解动态规划 (DynamicProgramming,DP) 方法的思想、求解策略及步骤。
作为挑战：可以考虑基于跳跃点的改进算法， 以及对连续型物品重量 /背包容量的支持。
实验目的
理解动态规划方法的核心思想以及动态规划方法的求解过程；
从算法分析与设计的角度，对 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
所选商品的一个序列为： 0 0 0 1 1
AAAAAA
精品文档
精品文档
4
精品文档
精品文档 你我共享
步骤2：算法设计
动态规划算法与分治法类似， 其基本思想是将待求解问题分解成若干个子问题， 然后从
这些子问题的解得到原问题的解。 与分治法不同的是， 适合于用动态规划法求解的问题， 经
分解得到的子问题往往不是互相独立的， 若用分治法解这类问题， 则分解得到的子问题数目
太多，以至于最后解决原问题需要耗费过多的时间。 动态规划法又和贪婪算法有些一样， 在
动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，
每采用一次贪婪准则便做出一个不可撤回的决策， 而在动态规划中，还要考察每个最优决策
序列中是否包含一个最优子序列。
步骤3：描述算法
1）编写voidValue(Typep[],Typew[],Typec,Typen,Typef[nMax][nMax])函数，用以计算各个最优子序列的值；
2）编写voidcompute(Typef[nMax][nMax],Typew[],Typep[],Typec,Typen,Typex[]) 函
数用以确