一、实验目的： １．通过动态规划算法的示例程序理解动态规划算法的基本思想； ２．运用动态规划算法解决实际问题加深对动态规划算法的理解和运用；
二、实验环境：VC++6.0
三、实验内容：1.源代码如下： #include #include #include<string.h> #include<stdio.h> using namespace std; #define N 105 int dp[N+1][N+1] ; char str1[N] , str2[N]; int maxx(int a , int b) { if(a > b) return a ; return b ; } int LCSL(int len1 , int len2) { int i , j ; int len = maxx(len1 , len2); for( i = 0 ; i <= len; i++ ) { dp[i][0] = 0 ; dp[0][i] = 0 ; } for( i = 1 ; i<= len1 ; i++) for( j = 1 ; j <= len2 ; j++) { if(str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][ j - 1] + 1 ; } else { dp[i][j] = maxx(dp[i - 1][ j ] , dp[i][j - 1]) ; } } return dp[len1][len2]; } void LCS(int i,int j) { if(i==-1||j==-1) return ; if(str1[i]str2[j]) { LCS(i-1,j-1); printf("%c “,str1[i]); } else if(dp[i-1][j]>dp[i][j-1]) LCS(i-1,j); else LCS(i,j-1); } int main() { while(cin >> str1 >> str2) { int len1 = strlen(str1) ; int len2 = strlen(str2) ; cout<<LCSL(len1 , len2)<<endl; LCS(len1,len2); } return 0; } 运行结果如下： 2.源代码如下： #include<stdio.h> #include<string.h> #define MaxNum 100 void MatrixChain(int p[MaxNum],int n,int m[MaxNum][MaxNum],int s[MaxNum][MaxNum]); void traceback(int i,int j,int s[MaxNum][MaxNum]); int main() { int P[MaxNum]; int N; int r; int M[MaxNum][MaxNum]; int S[MaxNum][MaxNum]; while(scanf(”%d",&N) && N!=0) { for(r=0;r<=N;r++) { scanf("%d",&P[r]); } MatrixChain(P,N,M,S); traceback(1,N,S); } return 0; } void MatrixChain(int p[MaxNum],int n,int m[MaxNum][MaxNum],int s[MaxNum][MaxNum]) { for (int i = 1; i <= n; i++) { m[i][i] = 0; } for (int r = 2; r <= n; r++) { for (int i = 1; i <= n - r+1; i++) { int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if (t < m[i][j]) { m[i][j] = t; s[i][j] = k; } } } } } void traceback(int i,int j,int s[MaxNum][MaxNum]) { if(ij) printf(“A%d”,i); else if (i==j-1) printf("(A%dA%d)",i,j); else { printf("("); traceback(i,s[i][j],s); traceback(s[i][j]+1,j,s); printf(")"); } } 运行结果如下： 3.动态规划法求解： #include using namespace std; #define max 50 void main() {int n,i; float a[max],b[max],sum=0; cout<<“请输入最大子段和的个数：”; cin>>n; cout<<endl; cout<<“请依次输入最大子段和数据：”<<endl; for(i=1;i<=n;i++) cin>>a[i]; cout<<endl; b[0]=a[0]; cout<<“求得最大子段和为：”; for(i=1;i<=n;i++) {if(b[i-1]>0) b[i]=b[i-1]+a[i]; else b[i]=a[i]; if(b[i]>sum) sum=b[i]; } cout<<sum<<endl<<endl; } 运行结果如下： 4.源代码如下： #include #include<stdio.h> using namespace std; #define N 20 int m[N][N]; char num[N]; int atoi(char arr[],int i,int j) { int sum=0; while(i<=j) { sum = sum*10+arr[i]-‘0’; return sum; } } int main() { int n,k,i,j,l,max,flag; while(cin>>n>>k) { for(i=1;i<=n;i++) cin>>num[i]; m[1][1]=num[1]-‘0’; for(i=2;i<=n;i++) m[i][1]=m[i-1][1]*10+(num[i]-‘0’); //初始化第一列 for(j=2;j<=k;j++)//按列进行初始化 { max=-1; for(i=1;i<=n;i++) { if(j>i) m[i][j]=0; else { for(l=j-1;l<=i-1;l++) { flag=m[l][j-1]atoi(num,l+1,i); if(flag>max) max=flag; } m[i][j]=max; } } } cout<<m[n][k]<<endl; } return 0; } 运行结果如下： 5.源代码如下： #include #include #define MAXN 2100+5 #define INF 10000000 int fmax[MAXN][MAXN],fmin[MAXN][MAXN],s[MAXN],n,max_ans=-INF,min_ans=INF; inline int maxx(int x,int y){return x>y?x:y;} inline int minn(int x,int y){return x<y?x:y;} void dp() { int i,j,k;
for(i=1;i<=2*n-1;++i) { for(j=1;j<=2*n-1;++j) { fmax[i][j]=-INF; fmin[i][j]=INF; } } for(i=1;i<=2*n-1;++i) fmax[i][i]=fmin[i][i]=0; for(i=2*n-1-1;i>=1;--i) { for(j=i+1;j<=2*n-1;++j) { for(k=i;k<=j-1;++k) { fmax[i][j]=maxx(fmax[i][j],fmax[i][k]+fmax[k+1][j]+s[j]-s[i-1]); fmin[i][j]=minn(fmin[i][j],fmin[i][k]+fmin[k+1][j]+s[j]-s[i-1]); } } }} void get_ans() { int i;
for(i=1;i<=n;++i) { //寻找长度为n的区间 max_ans=maxx(max_ans,fmax[i][i+n-1]); min_ans=minn(min_ans,fmin[i][i+n-1]); }} int main() { int i,temp;
scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%d",&temp); s[i]=s[i+n]=temp; } for(i=1;i<=2*n-1;++i) s[i]+=s[i-1];//前缀和优化 dp(); get_ans(); printf("%d\n%d\n",min_ans,max_ans); return 0;} 运行结果如下：
