1、实验二：动态规划实验目的：理解动态规划的基本思想，理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法，对较简单的问题能正确分析，设计出动态规划算法，并能快速编程实现。实验内容：编程实现讲过的例题：最长公共子序列问题、投资问题等。1 最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X=，则另一序列 Z=是 X 的子序列是指存在一个严格递增的下标序列 ，使得对于所有 j=1,2,k 有解答如下：a) 最长公共子序列的结构若用穷举搜索法，耗时太长，算法需要指数时间。易证最长公共子
2、序列问题也有最优子结构性质设序列 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
3、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;ili+1j)lij=lij-1;elselij=li-1j;return lmn;2.投资问题 例：某公司拟将 4 万元，向 A、B、C 三个项目追加投资，三个项目可以
4、有不同的投资额度，相应的效益值如表所示，问如何分配资金，才使总效益值最大？最优值：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 = Mon
5、ey; 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 + ValuestageMoney - splitmoney;if(tempmax temp)tempmax =temp;MaxValuestage - 1Money=tempmax;
