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

精品文档 你我共享
AAAAAA
0-1背包问题
实验内容
本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法 描述、算法正确性证明、算法分析、算法实现与测试) ，在针对精品文档 你我共享
AAAAAA
0-1背包问题
实验内容
本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法 描述、算法正确性证明、算法分析、算法实现与测试) ，在针对0-1背包问题求解的实践中
理解动态规划 (Dy namic P rogrammi ng, DP)方法的思想、求解策略及步骤。
作为挑战：可以考虑基于跳跃点的改进算法， 以及对连续型物品重量/背包容量的支持。
实验目的
理解动态规划方法的核心思想以及动态规划方法的求解过程；
从算法分析与设计的角度，对 0-1背包问题的基于 DP法求解有更进一步的理解。
环境要求
C, C++, Java，甚至于其他程序
对于环境没有特别要求。对于算法实现，可以自由选择 设计语言。
实验步骤
步骤 步骤 步骤 步骤 步骤 步骤 步骤
1：理解问题，
2：算法设计，
3：描述算法。
4：算法的正确性证明。 需要这个环节，在理解的基础上对算法的正确性给予证明;
5：算法复杂性分析，包括时间复杂性和空间复杂性；
6：算法实现与测试。附上代码或以附件的形式提交，
7：技术上、分析过程中等各种心得体会与备忘，
节中描述，步骤
给出问题的描述。
包括策略与数据结构的选择
希望采用源代码以外的形式，如伪代码或流程图等;
说明：步骤1-6在“实验结果”
同时贴上算法运行结果截图
需要言之有物。
7在“实验总结” 一节中描述。
精品文档 你我共享
AAAAAA
实验结果
步骤1：理解问题
其价值为Vi,问如何选择装入背包的
给定n和物品和一人背包，物品 i的重量是wi，
物品，使得装入背包的物品的总价值最大？
举例：
若商店一共有5类商品，重量分别为：3, 4，7, 8，9价值分别为：4, 5, 10, 11, 13则: 所选商品的最大价值为 24
精品文档 你我共享
AAAAAA
所选商品的一个序列为：
精品文档 你我共享
AAAAAA
步骤2:算法设计
动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题， 然后从 这些子问题的解得到原问题的解。 与分治法不同的是， 适合于用动态规划法求解的问题， 经 分解得到的子问题往往不是互相独立的， 若用分治法解这类问题，则分解得到的子问题数目■ 太多，以至于最后解决原问题需要耗费过多的时间。 动态规划法又和贪婪算法有些一样, 在 动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中， ' 每采用一次贪婪准则便做出一个不可撤回的决策， 而在动态规划中，还要考察每个最优决策 序列中是否包含一个最优子序列。
步骤3:描述算法
编写 void Value(Type p[], Type w[], Type c,Type n,Type f[nMax][nMax]) 函数，用以计 算各个最优子序列的值；
编写 void