文档介绍：实验二:动态规划
实验目的:理解动态规划的基本思想,理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的动态规划问题。掌握动态规划思想分析问题的一般方法,对较简单的问题能正确分析,设计出动态规划算法,并能快速编程实现。
实验内容:编程实现讲过的例题:最长公共子序列问题、投资问题等。
最长公共子序列
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=<x1, x2,…, xm>,则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列<i1, i2,…, ik>,使得对于所有j=1,2,…,k有
解答如下:
a) 最长公共子序列的结构
若用穷举搜索法,耗时太长,算法需要指数时间。
易证最长公共子序列问题也有最优子结构性质
设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>,则:
若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;
若xm≠yn且zk≠xm ,则Z是Xm-1和Y的最长公共子序列;
若xm≠yn且zk≠yn ,则Z是X和Yn-1的最长公共子序列。
其中Xm-1=<x1, x2, …, xm-1>,Yn-1=<y1, y2, …, yn-1>,Zk-1=<z1, z2, …, zk-1>。
最长公共子序列问题具有最优子结构性质。
注意:需要输出最长公共子序列
A:备忘录方法
程序如下:
#include<>
#include<>
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0') //约定第一个字符串以‘0’开始表示结束
break;
len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[] )
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;i<m+1;i++)
l[i][0]=0;
for(j=0;j<n+1;j++)
l[0][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(x[i]==y[j-1]) //i,j从1开始,但字符串是从0开始
l[i][j]=l[i-1][j]+1;
else if(l[i][j-1]>l[i+1][j])
l[i][j]=l[i][j-1];
else
l[i][j]=l[i-1][j];
return l[m][n];
}
例:某公司拟将4万元,向A、B、C三个项目追加投资,三个项目可以有不同的投资额度,相应的效益值如表所示,问如何分配资金,才使总效益值最大?最优值:190
A:递归