第3章 动态规划算法实验指导

第3章动态规划算法实验3.1动态规划算法的实现与时间复杂度测试实验目的编程实现经典的动态规划算法，理解动态规划算法设计的基本思想、程序实现的相关技巧，加深对动态规划算法设计与分析思想的理解。通过程序的执行时间测试结果，与理论上的时间复杂度结论进行对比、分析和验证。原理解析■动态规划算法的基本思想动态规划是一种在数学和计算机科学中使用的、用于求解包含重叠子问题的最优化问题的有效方法。其基本思想是：将原问题分解为相似的子问题，在求解的过程中通过子问题的解描述并求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域，在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题，为了避免多次解决这些子问题，它们的结果都逐渐被计算并保存，从小规模的子问题直到整个问题都被解决。因此，动态规划对每一子问题只做一次计算，具有较高的效率。■测试算法0-1背包问题是使用动态规划算法求解的代表问题，算法如下：KnapsackDP({w1,w2,…，wn),(v1,v2,…，vn}, C)fori=0tondom[i,0]=0endforforj=0toCdom[0,j]=0endforfori=1tondoforj=1toCdom[i,j]=m[i-1,j]ifwijthenm[i,j]=max{m[i,j],m[i-1,j-wi]+vi}endifendforendforreturnm[n,C]算法的时间复杂度为0(^Qo实验内容编程实现以上求解0-1背包问题的动态规划算法，并通过手动设置、生成随机数获得实验数据。记录随着输入规模增加算法的执行时间，分析并以图形方式展现增长率；测试、验证、对比算法的时间复杂度。实验步骤和要求编程实现以上算法，并进行测试，保证程序正确无误。其中，分别在程序开始和结束处设置记录系统当前时间的变量、用于计算程序执行的时间(以毫秒(ms)作为程序执行时间的计数单位)。测试C值不变的情形下随着n增加、程序执行时间增加的趋势。对于C=200、400、800、2000这四种情形，分别使用实验1中的随机数生成算法生成n个随机整数作为n个物品的重量，再生成n个随机整数作为n个物品的价值(n=10,20,40,100,200,400,800,2000)。对于每个C值，记录随着n增加程序的执行时间，并使用MSExcel图表绘制工具生成各不同C值情形下程序执行时间的对比曲线图(4条折线)。与理论上的时间复杂度结论进行对比分析，完成实验报告。

实验3.2动态规划算法的适应性测试1.实验目的对于同一问题，编程实现其分治算法和动态规划算法，通过对比分析，理解动态规划算法的适用情形。通过程序的执行时间测试结果，与理论结论进行对比、分析和验证。2.原理解析■分治算法与动态规划算法的对比：针对子问题是否重叠虽然很多问题均可分解为子问题、动态规划和分治算法都是通过子问题的解决来获得原问题的解。然而，分治算法适用于子问题不重叠（即相互独立）的情形，对于子问题重叠的情形分治法具有较高的时间复杂度，动态规划是针对这类情形的有效算法。■测试算法斐波纳契数列在现代物理、准晶体结构、化学等领域都有直接的应用。斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……，这个数列从第三项开始，每一项都等于前两项之和，即:'('(n)=〃(n-1)，f(n-2)n=1,2

n>3直观地，斐波纳契数列可递归地得到，算法如下:DAC_f(n)if(n==1)or(n==2)thenreturn1elsereturnf(n-1)+f(n-2)endif通过理论分析已经得出结论：以上递归算法随着n增大有指数计算时间。对于n的多项式个数的子问题，显然指数计算时间是不现实的。基于动态规划算法可高效地求解Fibonacci数问题，算法如下:DP_f(n)Initializef[1..n]fori=1tondoif(i==1)or(i==2)thenf[i]=1elsef[i]=f[i-1]+f[i-2]endifendforreturnf[n]算法的时间复杂度为。3)。实验内容编程实现以上求斐波纳契数的分治算法和动态规划算法。对于每个算法，记录随着斐波纳契数数列大小增加基本操作的执行次数，分析并以图形方式展现增长率；对比这两个算法，随着数列大小增加算法增长率的变化趋势；测试、验证、对比理论结论。实验步骤和要求“加法”是以上两个斐波纳契数算法的基本操作。编程实现以上DAC_f和DP_f算法，并进行测试，在其中设置加法执行次数的计数器变量。分别测试不同n值(n=5,10,15,20,25,30)情形下DAC_f和DP_f算法的加法次数，记录加法次数，并使用MSExcel图表绘制工具生成各不同n值情形下以上两个算法加法次数的对比曲线图(2条折线)。与两个算法时间复杂度的理论结论进行对比分析，总结分治与动态规划算法的适用条件和特点，