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

实验3. 基于动态规划方法求解0-1背包问题
实验内容
本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法描述、算法正确性证明、算法分析、算法实现与测试),在针对0-1背包问题求解的实践中理解动态规划(Dynamic Programming, 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
步骤2:算法设计
动态规划算法与分治法类似,其基本思想是将待求解问题分解成若干个子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的,若用分治法解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样,在动态规划中,可将一个问题的解决方案视为一系列决策的结果。不同的是,在贪婪算法中,每采用一次贪婪准则便做出一个不可撤回的决策,而在动态规划中,还要考察每个最优决策序列中是否包含一个最优子序列。
步骤3:描述算法
1)编写void Value(Type p[], Type w[], Type c,Type n,Type f[nMax][nMax])函数,用以计算各个最优子序列的值; 
2)pute(Type f[nMax][nMax], Type w[],Type p[], Type c, Type n, Type x[]) 函数用以确定计算装入的物品x[]和装入的物品的总重量totalWeight; 
3)编写主函数,控制输入输出; 4)改进和检验程序。
步骤4:算法的正确性证明
设(y1,y2,…,yn)是()(y2,…,yn)是下面相应子问题的一个最优解:
     证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,y