算法实验06动态规划

1、课程实验报告课程名称算法分析与设计班级实验日期姓名学号实验成绩实验名称实验6：动态规划的应用实 验 目 的 及 要 求1.理解动态规划算法的基本要素；2 .掌握动态规划的基本步骤；3.掌握动态规划的基本思想。实验环境操作系统：WindowsIDE： Visual C+实 验 内 容数塔问题从数塔的顶层出发，在每一个结点可以选择向左走或向右走，一直走到最底层， 要求找出一条路径，使得路径上的数值和最大。要求随机生成一个高度为N的 数塔(N=4,8,16,32)，分别用动态规划法和任一种其它方法(例如蛮力法、回 溯法、分治法等)进行求解，分析两种方法的时间复杂度，并画出时间随N变 化的曲线图。动态

2、规划运行过程试过程v 1 I 3 -V IT 5W MT 、J V3378 92?1 36 7827 34 73 15100 50 27 39 2949 13 15 8 18 2330 54 24 47 56 27 757 6 44 59 50 57 80 36最大值为：476最大值的路径为：33789127100495444所用时间为：。毫秒3378 92?1 36 7827 34 73 15100 50 27 39 2949 13 15 8 13 2330 54 24 47 56 27 757 6 44 59 50 57 80 363H 04 亍蛀 S AO CH OO f!7 O1运行到

3、一定规模：位W4471明%处4tJ&95678082879132975557833779939669915096 SO 6754858272507*9872947373347760768286987152991009556783所用时间为：4毫秒7294 605 2893 53 41 9164 17 94 3? 2018 1 53 65 65 3781 33 84 74 47 93 19C 44 M2 44 OT C4 母M采用递归算法：|J J 4/ 4Z00744uIV4086 81 40 315304510988686657038 2 45 93811355743844959347597

4、8 85 55 5661 6228 45 36 4 7179555 97 98 14 60 62 55 21 65 94 97 35 55 17 65最大路径值为：1059所用时间为：15毫秒5861 1063 12 7663 39 30 10033 23 58 7 2199 15 12 83 6159 10 100 75 5 65 61S9 6 25 24 48 66 98 29总结通过分析动态规划的状态转移方程dpij = max(dpi + 1j, dpi + 1j+1) + dataij,最后的结果保存在dp00中，可以得出时间复杂度为：O(n), 而采用递归的方法，运行到规模为32的

5、就显得比较吃力。l2E+091E+09/r600000000/一200000000/123456789附录#include#include #include#include#include#define MAX 1000using namespace std;int N; /输入规模clock_t begintimes, endtimes; /clock_t为clock()函数返回的变量类型double duration;/运行时间计算随机数产生int number()(int a = rand() % 100 + 1;return a;定义结构体typedef struct (int x,

6、y;int value;Node;定义一个二维数组存储塔Node AMAXMAX;Node BMAXMAX;输出函数，两重for循环输出void show()(for (int i = 0; i N; i+)(for (int j = 0; j=i; j+)cout Aij.value ”;cout endl;初始化函数void init()(srand(unsigned)time(NULL); /给一个时间种子for (int i = 0; i N; i+)(for (int j = 0; j = i; j+)(Aij.value = number();return;/动态规划函数void

7、dp()(begintimes = clock(); /计时开始int t, x1, y1; /临时计数for (int m = 0; mN; m+) /初始化B结构体数组for (int n = 0; n= 0; j-) for (int i = 0; i Aj + 1i + 1.value) /当前数大于 后边数t = Aj + 1i.value; /规划Aji.x = j + 1;Aji.y = i;else/当前数小于后边数t = Aj + 1i + 1.value;Aji.x = j + 1; 规划 Aji.y = i + 1;Aji.value = Aji.value + t;en

8、dtimes = clock();/计时结束x1 = A00.x;y1 = A00.y;cout 最大值为： A00.value endl;cout最大值的路径为：endl;coutB00.value”;for (int i = 0; iN-1; i+)(t = x1;coutBx1y1.value” ;x1 = Aty1.x;y1 = Aty1.y;cout endl;/回溯递归求解，较简单，但是时间复杂度高int MaxSum(int l, int r)if (l = N)return Alr.value;elsereturn max(MaxSum(l + 1, r), MaxSum(l

9、+ 1, r + 1) + Alr.value;/主函数int main()N = 4;do (N *= 2; 依次增大输入规模init(); /进行初始化show(); 进行原始塔展示这里是递归回溯法begintimes = clock(); /计时开始 int result=MaxSum(0,0);endtimes = clock(); /计时结束cout 最大路径值为： result endl;/dp();/动态规划求解duration = 1000 * (double)(endtimes - begintimes) / CLK_TCK; /总共 用时(毫秒)cout 所用时间为： duration 毫秒” endl;记录实验结果，注意运行一次手动进行数据转移，清除数据/