实验二 动态规划算法

实验二 动态规划算法基本题一：最长公共子序列问题一、实验目的与要求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)实验源代码:/最长公共子序问题:/问题描述: 若给定序列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的最长公共子序列。 #includeusing namespace std;#define max 1000/注意：这里使用的char数组，可以按字符输出，若改为string类型，/执行printf(%c,Am-1)就会报错; char A100,B100; /输入的两个串a和b/这里定义全局变量可以不赋值0，因为全局变量自动赋值0; int cmaxmax; /记录最长公共子序的长度； int bmaxmax; /记录状态号; void LCS(int m,int n)if(m=0|n=0)return;else if(bmn=1)LCS(m-1,n-1);printf(%c,Am-1); else if(bmn=2)m=m-1;LCS(m,n);else if(bmn=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=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;int main()printf(请输入两个待测的字符串:n);scanf(%s,&A); scanf(%s,&B);int m=strlen(A); /m为A串长度； int n=strlen(B); /n为B串长度; LCS_length(m,n);printf(其最长公共子序的长度为:%dn,cmn);printf(其最长公共子序为:);LCS(m,n);return 0;(2)运行结果为:(3)算法思路:最长公共子序列的结构有如下表示：设序列X=和Y=的一个最长公共子序列Z=，则：1. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；2. 若xmyn且zkxm ，则Z是Xm-1和Y的最长公共子序列；3. 若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。其中Xm-1=，Yn-1=，Zk-1=。基本题二：最大字段和问题一、实验目的与要求1、熟悉最长最大字段和问题的算法；2、进一步掌握动态规划算法；二、实验题若给定n个整数组成的序列a1，a2，a3，an，求该序列形如aiai1an的最大值。三，实验源代码:#include#define max 1000using namespace std;int N; /表示一个数组的长度值;int dpmax; /记录以i为结尾的最大子段和; /通过dp数组记录最优下标的start和end; void Maxsum(int a)int maxx=0;int end,start;for(int i=1;i0)dpi=dpi-1+ai;elsedpi=ai;if(maxx=0;i-)if(dpi=0)start=i;elsebreak;i+;start=i;printf(MaxSum:%dn,dpend);printf(Best start:%dn,start);printf(Best end:%dn,end);int main()printf(请输入一组数据的元素个数:);scanf(%d,&N);int *a=new int N+1;printf(请输入元素的值:);for(int i=1;i=N;i+)scanf(%d,&ai);Maxsum(a);delete a;return 0;（2）运行结果:(3)算法思路:其实，我们在选择一个元素aj的时候，只有两种情况，将ai至aj-1加上，或者从aj以j为起点开始。我们用一个数组dpi表示以i为结束的最大子段和，对于每一个ai，加上dpi-1成为子段，或以ai开始成为新段的起点。因为我们只需要记录dp值，所以复杂度是O(n)。这就是最大子段和的动态规划算法。我们甚至不需要dp数组，只需要定义一个dp变量，因为最后要求的dp值也是最大的，所以我们可以在求dp的时候更新为最大的。提高题一： 用动态规划法求解0/1背包问题一、实验要求与目的1、 掌握动态规划算法求解问题的一般特征和步骤。2、 使用动态规划法编程，求解0/1背包问题。二、实验内容1、 问题描述：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？2、 算法描述。3、 程序实现；给出实例测试结果。三.(1)实验源代码:/用动态规划的方法求解0/1背包问题/要求:/input:n 表示总共有n种物品/ W 表示每种物品的重量/ V 表示每种物品的价值/ c 表示背包的容量 #includeusing namespace std;int n,c;int dp10051005;void Knapsack(int V,int W,int c,int n,int dp1005)int i,j;int jMax=min(Wn-1,c); /这里必须是Wn-1,否则，在Wn-1时刻也是合法情况; for(j=0;j=jMax;j+)dpnj=0; /i=n,jwn;for(j=Wn;j1;i-)jMax=min(Wi-1,c);for(j=0;j=jMax;j+)dpij=dpi+1j; /若小于当前的背包容量，则不装入; for(j=Wi;j=W1)dp1c=max(dp1c,dp2c-W1+V1);void Traceback(int dp1005,int W,int c,int n,int x)/x数组用来存放是否第i个元素被装栽进来for(int i=1;in;i+)if(dpic=dpi+1c)xi=0;elsexi=1;c=c-Wi; xn=(dpnc)?1:0;for(int i=1;i=n;i+)if(xi=1)printf(第%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;W0=0,V0=0,x0=0;printf(请输入每个物品的重量:n);for(int i=1;i=n;i+)scanf(%d,&Wi);printf(请输入每个物品的价值:n); for(int i=1;i=n;i+)scanf(%d,&Vi);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) jwi(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi;(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。 11 / 11