实验 二 动态规划算法
基本题一：最长公共子序列问题 一、实验目的与要求 1 1 、熟悉最长公共子序列问题的算法； 2 2 、初步掌握动态规划算法； 二、实验题
若给定序列 X={x1,x2, … ,xm} ，则另一序列 Z={z1,z2, … ,zk} ，是 X X 的子序列是指存在一个严格递增下标序列 {i1,i2, … ,ik} 使得对于所有 j=1,2, …k ,k 有：
zj=xij 。例如，序列 Z={B ，C C ，D D ， B} 是序列 X={A ，B B ，C C ，B B ，D D ，A A ， B} 的子序列，相应的递增下标序列为 {2 ，3 3 ，5 5 ， 7} 。
给定 2 2 个序列 X X 和 和 Y Y ，当另一序列 Z Z 既是 X X 的子序列又是 Y Y 的子序列时，称 Z Z是序列 X X 和 和 Y Y 的公共子序列。
给定 2 2 个序列 X={x1,x2, … ,xm}和 和 Y={y1,y2, … ,yn} ，找出 X X 和 和 Y Y 的最长公共子序列。
三． (1) 实验源代码: : // 最长公共子序问题: : // 问题描述 :
若给定序列 X={x1,x2, … ,xm} ，则另一序列 Z={z1,z2, … ,zk} ， //是 是 X X 的子序列是指存在一个严格递增下标序列 {i1,i2, … ,ik} 使得对于所有j=1,2, …k ,k 有：
zj=xij 。
// 例如，序列 Z={B ，C C ，D D ， B} 是序列 X={A ，B B ，C C ，B B ，D D ，A A ， B} 的子序列 ，相应的递增下标序列为 {2 ，3 3 ，5 5 ， 7} 。
// 给定 2 2 个序列 X X 和 和 Y Y ，当另一序列 Z Z 既是 X X 的子序列又是 Y Y 的子序列时，称
Z Z 是序列 X X 和 和 Y Y 的公共子序列。
// 给定 2 2 个序列 X={x1,x2, … ,xm}和 和 Y={y1,y2, … ,yn} ，找出 X X 和 和 Y Y 的最长公共子序列。
#include<bits/stdc++.h> using namespace std; #define max 1000
// 注意：这里使用的 r char 数组，可以按字符输出，若改为 g string 类型， // 执行 printf("%c",A[m- - 1]) 就会报错; ;
char A[100],B[100];
// 输入的两个串 a a 和 和 b b
// 这里定义全局变量可以不赋值 0 0 ，因为全局变量自动赋值 0;
int c[max][max]; // 记录最长公共子序的长度；
int b[max][max]; // 记录状态号;
void LCS(int m,int n) { {
if(m==0||n==0)
{ {
return;
} }
else if(b[m][n]==1)
{ {
LCS(m- - 1,n- - 1);
printf("%c",A[m- - 1]);
} }
els e if(b[m][n]==2)
{ {
m=m- -; 1;
LCS(m,n);
} }
else if(b[m][n]==3)
{ {
n=n- -; 1;
LCS(m,n);
} } } }
void LCS_length(int m,int n) { {
for(int i=1;i<=m;i++)
{ {
for(int j=1;j<=n;j++)
{ {
if(A[i- - 1]==B[j- - 1])
{ {
c[i][j]=c[i- - 1][j- - 1]+1;
b[i][j]=1;
} }
else if(c[i- - 1][j]>=c[i][j- - 1])
{ {
c[i][j]=c[i- - 1][j];
b[i][j]=2;
} }
else
{ {
c[i][j]=c[i][j- - 1];
b[i][j]=3;
} }
} }
} }
} }
int main() { {
printf(" 请输入两个待测的字符串: :\ \ n");
scanf("%s",&A);
scanf("%s",&B);
int m=strlen(A);
//m 为 为 A A 串长度；
n int n=strlen(B);
//n 为 为 B B 串长度;
LCS_length(m,n);
printf(" 其最长公共子序的长度为 :%d\ \ n",c[m][n]);
printf(" 其最长公共子序为 :");
LCS(m,n);
return 0; } } (2) 运行结果为: :
(3) 算法思路: : 最长公共子序列的结构有如下表示：
设序列 X=<x 1 1 , x 2 2 , …, x m m > > 和 Y=<y 1 1 , y 2 2 , …, y n n > > 的一个最长公共子序列Z=<z 1 1 , z 2 2 , …, z k k > > ，则：
1. 若 若 x x m m =y n n ，则 z z k k =x m m =y n n 且 Z Z k k- -1 1 是 是 X X m m- -1 1 和 和 Y Y n n- -1 1 ； 的最长公共子序列； 2. 若 若 x x m m ≠y n n 且 且 z z k k ≠x m ， 则 Z Z 是 X X m m- -1 1 和 和 Y Y 的最长公共子序列； 3. 若 若 x x m m ≠y n n 且 且 z z k k ≠y n n
，则 Z Z 是 是 X X 和 和 Y Y n n- -1 1 的最长公共子序列。
其中 X X m m- -1 1 =<x 1 1 , x 2 2 , …, x m m- -1 1 > >， ，Y Y n n- -1 1 =<y 1 1 , y 2 2 , …, y n n- -1 1 > >， ，Z Z k k- -1 1 =<z 1 1 , z 2 2 , …, z k k- -1 1 > >。
。
基本题二：最大字段和问题
一、实验目的与要求 1 1 、熟悉最长最大字段和问题的算法； 2 2 、进一步掌握动态规划算法； 二、实验题 若给定 n n 个整数组成的序列 a a 1 1 ，a a 2 2 ，a a 3 3 ，……a a n n ，求该序列形如 a a i i ＋a a i i ＋1 1 ＋……＋a a n n 的最大值。
三，实验源代码: : #include<bits/stdc++.h> #define max 1000 using namespace std;
int N;
// 表示一个数组的长度值; ;
int dp[max];
// 记录以 i i 为结尾的最大子段和;
// 通过 d dp p 数组记录最优下标的 t start 和 和 end;
void Maxsum(int a[]) { {
int maxx=0;
int end,start;
for(int i=1;i<=N;i++)
{ {
if(dp[i- - 1]>0)
{ {
dp[i]=dp[i- - 1]+a[i];
} }
else
{ {
dp[i]=a[i];
} }
if(maxx<=dp[i])
{ {
maxx=dp[i];
end=i;
} }
} }
start=end;
int i;
for(i=start- - 1;i>=0;i- --) )
{ {
if(dp[i]>=0)
{ {
start=i;
} }
else
{ {
break;
} }
} }
i++;
start=i;
printf("MaxSum:%d\ \ n",dp[end]);
printf("Best start:%d\ \ n",start);
printf("Best end:%d\ \ n",end); } }
int main() { {
printf(" 请输入一组数据的元素个数 :");
scanf( "%d",&N);
int *a=new int [N+1];
printf(" 请输入元素的值 :");
for(int i=1;i<=N;i++)
{ {
scanf("%d",&a[i]);
} }
Maxsum(a);
delete a;
return 0; } } （2 2 ）
运行结果: :
(3) 算法思路: : 其实，我们在选择一个元素 a[j] 的时候，只有两种情况，将 a[i]至 至 a[j- -] 1] 加上，或者从 从 a[j]以 以 j j 为起点开始。我们用一个数组 dp[i] 表示以 i i 为结束的最大子段和，对于每一个 [ a[] i] ，加上 dp[i- -] 1] 成为子段，或以 a[i] 开始成为新段的起点。因为我们只需要记录 p dp 值，所以复杂度是 O(n) 。
这就是最大子段和的动态规划算法。
我们甚至不需要 p dp 数组，只需要定义一个 p dp 变量，因为最后要求的 p dp 值也是最大的，所以我们可以在求 p dp 的时候更新为最大的。
提高题一：
用动态规划法求解 1 0/1 背包问题
一、实验要求与目的 1、 、 掌握动态规划算法求解问题的一般特征和步骤。
2、 、 使用动态规划法编程，求解 1 0/1 背包问题。
二、实验内容 1、 、 问题描述：给定 n n 种物品和一个背包，物品 i i 的重 量是 W i i ，其价值为 V V i i ，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？ 2、 、 算法描述。
3、 、 程序实现；给出实例测试结果。
三 .(1) 实验源代码: : // 用动态规划的方法求解 1 0/1 背包问题 // 要求: : //input:n 表示总共有 n n 种物品 //
W 表示每种物品的重量 //
V 表示每种物品的价值 //
c 表示背包的容量
#include<bits/stdc++.h> using namespace std;
int n,c; int dp[1005][1005; ];
void Knapsack(int V[],int W[],int c,int n,int dp[][1005]) { {
int i,j;
int jMax=min(W[n]- - 1,c);
// 这里必须是 W[n]- -, 1, 否则，在 W[n- -] 1] 时刻也是合法情况;
for(j=0;j<=jMax;j++)
{ {
dp[n][j]=0;
//i=n,j<wn;
} }
for(j=W[n];j<=c;j++)
{ {
dp[n][j]=V[n];
} }
for(i=n- -1 1 ;i>1;i- --) )
{ {
jMax=min(W[i]- - 1,c);
for(j=0;j<=jMax;j++)
{ {
dp[i][j]=dp[i+1][j];
// 若小于当前的背包容量，则不装入;
} }
for(j=W[i];j<=c;j++)
{ {
dp[i][j]=max(dp[i+1][j],dp[i+1][j- - W[i]]+V[i]);
// 比较装入的代价，谋求最大代价;
} }
} }
dp[1][c]=dp[2][c];
if(c>=W[1])
{ {
dp[1][c]=max(dp[1][c],dp[2][c- - W[1]]+V[1]);
} } } }
void Traceback(int dp[][1005],int W[],int c,int n,int x[]) { {
x //x 数组用来存放是否第 i i 个元素被装栽进来
for(int i=1;i<n;i++)
{ {
if(dp[i][c]==dp[i+1][c])
{ {
x[i]=0;
} }
else
{ {
x[i]=1;
c=c- - W[i];
} }
}
x x [n]=(dp[n][c])?1:0;
for(int i=1;i<=n;i++)
{ {
if(x[i]==1)
{ {
printf(" 第d %d 个物品装入\ \ n",i);
} }
} } } }
int main() { {
printf(" 请输入物品的数量和背包的容量 :");
scanf("%d %d",&n,&c);
int *W=new int [n];
int *V=new int [n];
int *x=new int [n];
W[0]=0,V[0]=0,x[0]=0;
printf(" 请输入每个物品的重量: :\ \ n");
for(int i=1;i<=n;i++)
{ {
scanf("%d",&W[i]);
} }
printf(" 请输入每个物品的价值: :\ \ n");
for(int i=1;i<=n;i++)
{ {
scanf("%d",&V[i]);
} }
Knapsack(V,W,c,n,dp);
Traceback(dp,W,c,n,x);
return 0; } } (2) 运行结果: :
(3) 算法思路：
令 V(i,j)表示在前 i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1)
V(i,0)=V(0,j)=0
(2)
V(i,j)=V(i-1,j)
j<w i
V(i,j)=max{V(i-1,j) ,V(i-1,j-w i )+v i ) } j>w i
(1)式表明：如果第 i 个物品的重量大于背包的容量，则装人前 i 个物品得到的最大价值和装入前 i-1 个物品得到的最大价是相同的，即物品 i 不能装入背包；第(2)个式子表明:如果第 i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第 i 个物品装入背包，则背包物品的价值等于第 i-1 个物品装入容量位 j-w i
的背包中的价值加上第 i 个物品的价值 v i;
(b)如果第 i 个物品没有装入背包，则背包中物品价值就等于把前 i-1 个物品装入容量为 j 的背包中所取得的价值。显然，取二者中价值最大的作为把前 i 个物品装入容量为 j 的背包中的最优解。