实验二：动态规划.doc

实验二：动态规划实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。实验内容：编程实现讲过的例题：最长公共子序列问题、投资问题等。1 最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=，则另一序列Z=是X的子序列是指存在一个严格递增的下标序列 ，使得对于所有j=1,2,k有解答如下：a) 最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共子序列问题也有最优子结构性质设序列X=和Y=的一个最长公共子序列Z=，则：i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； ii. 若xmyn且zkxm ，则Z是Xm-1和Y的最长公共子序列； iii. 若xmyn且zkyn ，则Z是X和Yn-1的最长公共子序列。 其中Xm-1=，Yn-1=，Zk-1=。最长公共子序列问题具有最优子结构性质。注意：需要输出最长公共子序列A:备忘录方法B动态规划算法 程序如下：#include#includeint lcs_length(char x, char y);int main()char x100,y100;int len;while(1)scanf(%s%s,x,y);if(x0=0) /约定第一个字符串以0开始表示结束break;len=lcs_length(x,y);printf(%dn,len);int lcs_length(char x, char y )int m,n,i,j,l100100;m=strlen(x);n=strlen(y);for(i=0;im+1;i+)li0=0;for(j=0;jn+1;j+)l0j=0;for(i=1;i=m;i+)for(j=1;jli+1j)lij=lij-1;elselij=li-1j;return lmn;2.投资问题 例：某公司拟将4万元，向A、B、C三个项目追加投资，三个项目可以有不同的投资额度，相应的效益值如表所示，问如何分配资金，才使总效益值最大？最优值：190A:递归方法（自顶向下）+备忘录#include using namespace std;int Value35=47,51,59,71,76,49,52,61,71,78,46,70,76,88,88;int MaxValue(int Stage, int Money) int splitmoney = 0; int tempmax=0; int temp = 0; if(Stage = 1)/边界条件 return Value0Money; for(splitmoney = 0 ; splitmoney = Money; splitmoney+) temp = MaxValue(Stage - 1, splitmoney) + ValueStage splitmoney; if(tempmax temp) tempmax = temp; return tempmax;void main()cout MaxValue(3,4);B:动态规划算法（自底向上, 本质上即状态转移方程的非递归实现？）核心伪代码：int Value35=47,51,59,71,76,49,52,61,71,78,46,70,76,88,88;int Money = 4;int MaxValue35 =0;int temp = 0;int tempmax = 0;for(int i = 0; i 5; i+) MaxValue0i = Value0i;for(int stage = 2; stage =3; stage+)for(int splitmoney = 0 ; splitmoney = Money; splitmoney+) temp = MaxValuestagesplitmoney + V