算法设计与分许-动态规划实验报告.docx

西 安 邮 电 大 学（计算机学院）课内实验报告实 验： 动态规划 课程：算法设计与分析班 级：学号：学生姓名 ：任课教师：一、实验目的1.理解动态规划算法的概念2.掌握动态规划算法的基本要素3.掌握设计动态规划算法的步骤4.通过应用学习动态规划算法的设计技巧与策略二、实验内容1.时间复杂度O(nlongn)实现最长递增子序列2.0-1背包问题3.数字三角形问题三、实验环境MAC OS四、实验结果1.2.3.五、评价分析及心得体会通过这几次算法实验，我熟悉并掌握了几种经典算法的应用，并通过上机实践熟练了c+编程，熟练了自己的动手能力，感觉受益不少。平常要多写代码，认真预习实验内容，否则很容易浪费上机的时间。六、源代码1.#include #include using namespace std; void printSequence(int *b,int* nums,int last); int main() int nums=1,7,8,9,2,3,4,5; /数组b存储在递增子序列中当前元素的前一个元素序号 int n = sizeof(nums) / sizeof(int); int *b=new intn; /vector容器last中存储各不同长度的递增子序列(同一长度的子序列，只考虑尾元素最小的序列) / 中最后一个元素的序号 vector last; last.push_back(0); b0=0; for (int i=1;inumslasthigh) /如果当前元素比last中所有元素都大则最长递增子序列的长度加一，其尾元素为当前元素numsi last.push_back(i); bi=lasthigh; else/否则使用二分法在last中查找到大于等于当前元素numsi的最小元素 while(lownumslastmiddle) low=middle+1; else high=middle-1; /更新last中的元素值 if(numsinumslastlow) pos=low+1; else pos=low; lastpos=i; bi=lastpos-10 ? 0 : pos-1; cout原序列长度为n，如下：endl; for (int i=0;in;i+) coutnumsi ; int len=last.size(); coutendl最长递增子序列长度为len，如下：endl; printSequence(b,nums,lastlen-1); coutendl; delete b; return 0; void printSequence(int *b,int* nums,int last) if(blast!=last) printSequence(b,nums,blast); coutnumslast ; 2.#include using namespace std; /* * ciw表示背包容量为w时，i个物品导致的最优解的总价值，大小为(n+1)*(w+1) * vi表示第i个物品的价值，大小为n * wi表示第i个物品的重量，大小为n * */ void DP(int n, int W, int c18, int *v, int *wei) memset(*c, 0, (W+1)*sizeof(int); for (int i = 1; i = n; i+) ci0 = 0; for (int w = 1; w w) /此处比较是关键 ciw = ci-1w; else int temp = ci-1w-weii-1 + vi-1; /注意wei和v数组中的第i个应该为weii-1和vi-1 if (ci-1w temp) ciw = ci-1w; else ciw = temp; void findPath(int c18, int *x, int *wei, int n, int W) int w = W; for (int i = n; i = 2; i-) if (ciw = ci-1w) xi-1 = 0; else xi-1 = 1; w = w - weii-1; if (c1w = 0) x0 = 0; else x0 = 1; int main() int n = 5; int W = 17; int w = 3, 4, 7, 8, 9; int v = 4, 5, 10, 11, 13; int c618 = 0; DP(n, W, c, v, w); coutc517endl; int x5; findPath(c, x, w, n, W); for (int i = 0; i n; i+) coutxi ; 3.#include #include #define MAX_NUM 100 int DMAX_NUM + 10MAX_NUM + 10; int N; int aMaxSumMAX_NUM + 10MAX_NUM + 10; int main() int i, j; scanf(%d, & N); for( i = 1; i = N; i + ) for( j = 1; j = i; j + ) scanf(%d, &Dij); for( j = 1; j 1 ; i - ) for( j