实验二 动态规划算法

实验二 动态规划算法

基本题一：最长公共子序列问题 一、实验目的与要求

1、熟悉最长公共子序列问题的算法；

2、初步掌握动态规划算法；

二、实验题

若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

三．(1)实验源代码:

//最长公共子序问题:

1 / 23

//问题描述: 若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，

//是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。

//例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

//给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。

//给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

#include

using namespace std;

#define max 1000

//注意：这里使用的char数组，可以按字符输出，若改为string类型，

//执行printf(\"%c\就会报错;

char A[100],B[100]; //输入的两个串a和b

2 / 23

//这里定义全局变量可以不赋值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\

3 / 23

}

else 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)

4 / 23

{

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];

5 / 23

b[i][j]=2;

}

else

{

c[i][j]=c[i][j-1];

b[i][j]=3;

}

}

}

}

int main()

{

printf(\"请输入两个待测的字符串:\\n\");

6 / 23

scanf(\"%s\

scanf(\"%s\

int m=strlen(A); //m为A串长度；

int n=strlen(B); //n为B串长度;

LCS_length(m,n);

printf(\"其最长公共子序的长度为:%d\\n\

printf(\"其最长公共子序为:\");

LCS(m,n);

return 0;

}

(2)运行结果为:

7 / 23

(3)算法思路:

最长公共子序列的结构有如下表示：

设序列X=和Y=的一个最长公共子序列Z=，则：

1. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；

2. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；

3. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

8 / 23

基本题二：最大字段和问题 一、实验目的与要求

1、熟悉最长最大字段和问题的算法；

2、进一步掌握动态规划算法；

二、实验题

若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。

三，实验源代码:

#include

#define max 1000

using namespace std;

int N; //表示一个数组的长度值;

9 / 23

int dp[max]; //记录以i为结尾的最大子段和;

//通过dp数组记录最优下标的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

10 / 23

{

dp[i]=a[i];

}

if(maxx<=dp[i])

{

maxx=dp[i];

end=i;

}

}

start=end;

int i;

for(i=start-1;i>=0;i--)

{

11 / 23

if(dp[i]>=0)

{

start=i;

}

else

{

break;

}

}

i++;

start=i;

printf(\"MaxSum:%d\\n\

printf(\"Best start:%d\\n\

12 / 23

printf(\"Best end:%d\\n\

}

int main()

{

printf(\"请输入一组数据的元素个数:\");

scanf(\"%d\

int *a=new int [N+1];

printf(\"请输入元素的值:\");

for(int i=1;i<=N;i++)

{

scanf(\"%d\

}

Maxsum(a);

13 / 23

delete a;

return 0;

}

（2）运行结果:

(3)算法思路:

其实，我们在选择一个元素a[j]的时候，只有两种情况，将a[i]至a[j-1]加上，或者从a[j]以j为起点开始。我们用一个数组dp[i]表示以i为结束的最大子段和，对于每一个a[i]，加上dp[i-1]成为子段，或以a[i]开始成为新段的起点。因为我们只需要记录dp值，所以复杂度是O(n)。

14 / 23

这就是最大子段和的动态规划算法。

我们甚至不需要dp数组，只需要定义一个dp变量，因为最后要求的dp值也是最大的，所以我们可以在求dp的时候更新为最大的。

提高题一： 用动态规划法求解0/1背包问题 一、实验要求与目的

1、 掌握动态规划算法求解问题的一般特征和步骤。

2、 使用动态规划法编程，求解0/1背包问题。

二、实验内容

1、 问题描述：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？

2、 算法描述。

3、 程序实现；给出实例测试结果。

三.(1)实验源代码:

//用动态规划的方法求解0/1背包问题

15 / 23

//要求:

//input:n 表示总共有n种物品

// W 表示每种物品的重量

// V 表示每种物品的价值

// c 表示背包的容量

#include

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]时刻也是合法情况;

16 / 23

for(j=0;j<=jMax;j++)

{

dp[n][j]=0; //i=n,j}

for(j=W[n];j<=c;j++)

{

dp[n][j]=V[n];

}

for(i=n-1;i>1;i--)

{

jMax=min(W[i]-1,c);

for(j=0;j<=jMax;j++)

{

17 / 23

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]);

}

}

//比较装入的代价，谋求最大 18 / 23

void Traceback(int dp[][1005],int W[],int c,int n,int x[])

{

//x数组用来存放是否第i个元素被装栽进来

for(int i=1;i{

if(dp[i][c]==dp[i+1][c])

{

x[i]=0;

}

else

{

x[i]=1;

c=c-W[i];

19 / 23

}

}

x[n]=(dp[n][c])?1:0;

for(int i=1;i<=n;i++)

{

if(x[i]==1)

{

printf(\"第%d个物品装入\\n\

}

}

}

int main()

{

20 / 23

printf(\"请输入物品的数量和背包的容量:\");

scanf(\"%d %d\

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\

}

printf(\"请输入每个物品的价值:\\n\");

for(int i=1;i<=n;i++)

21 / 23

{

scanf(\"%d\

}

Knapsack(V,W,c,n,dp);

Traceback(dp,W,c,n,x);

return 0;

}

(2)运行结果:

22 / 23

(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) jV(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi

(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。

23 / 23