搜档网
当前位置:搜档网 › 用动态规划法解决最长公共子序列问题

用动态规划法解决最长公共子序列问题

用动态规划法解决最长公共子序列问题
用动态规划法解决最长公共子序列问题

动态规划解最长子序列

一、课程设计目的

掌握动态规划法的原理,并能够按其原理编程实现求两个序列数据的最长公共子系列,以加深对其的理解。

二、课程设计内容

1、用动态规划法解决最长子序列问题

2、交互输入两个序列数据

3、输出两个序列的最长公共子序列

三、概要设计

四、详细设计与实现

#include "iostream.h"

#include "iomanip.h"

#define max 100

void LCSLength(int m,int n,char *x,char *y,char *b)

{

int i,j,k;

int c[max][max];

for(i=1;i<=m;i++)

{

c[i][0]=0;

}

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

{

c[0][i]=0;

}

for(i=1;i<=m;i++)

{

for(j=1;j<=n;j++)

{

if(x[i-1]==y[j-1])

{

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

k=i*(n+1)+j;

b[k]='\\';

}

else if(c[i-1][j]>=c[i][j-1])

{

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

k=i*(n+1)+j;

b[k]='|';

}

else{

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

k=i*(n+1)+j;

b[k]='-';

}

}

}

}

void LCS(int i,int j,char *x,char *b,int width) {

if(i==0 || j==0)

return;

int k=i*(width+1)+j;

if(b[k]=='\\'){

LCS(i-1,j-1,x,b,width);

cout<

}

else if(b[k]=='|')

{

LCS(i-1,j,x,b,width);

}

else

{

LCS(i,j-1,x,b,width);

}

}

void main()

{

char x[max]={'a','b','c','b','d','a','b'};

char y[max]={'b','d','c','a','b','a'};

int m=7;

int n=6;

char b[max]={0};

LCSLength(m,n,x,y,b);

LCS(m,n,x,b,n);

cout<

}

最长公共子序列问题具有最优子结构性质

X = { x1 , ... , xm }

Y = { y1 , ... , yn }

及它们的最长子序列

Z = { z1 , ... , zk }

1、若 xm = yn ,则 zk = xm = yn,且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列

2、若 xm != yn ,且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列

3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列

由性质导出子问题的递归结构

当 i = 0 , j = 0 时 , c[i][j] = 0

当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1

当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

#include

#define max(a,b) a>b?a:b

#define M 100

void display(int &n,int &C,int w[M],int v[M])

{

int i;

cout<<"请输入物品种数n:";

cin>>n;

cout<

cout<<"请输入背包总容量C:";

cin>>C;

cout<

cout<<"请输入各物品的大小或重量w:"<

w[0]=0;

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

cin>>w[i];

cout<<"请输入各物品其价值v:"<

v[0]=0;

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

cin>>v[i];

};

int knapsack(int &n,int &C,int w[M],int v[M],int V[M][M]) {

int i,j;

for (i=0;i<=n;i++)

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

{

if(i==0||j==0)

V[i][j]=0;

else if(w[i]>j)

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

else if(w[i]<=j)

V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);

}

return V[n][C];

};

void traceback(int n,int C,int w[M],int x[M],int V[M][M]) {

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

{

if(V[i][C]==V[i-1][C])

x[i]=0;

else

{

x[i]=1;

C=C-w[i];

}

}

//x[n]=(V[n][C]>0)?1:0;

};

void main()

{

int i,j,n,C;

char ch;

int w[M],v[M],x[M];

int V[M][M];

while(1)

{

display(n,C,w,v);

cout<<"运算结果如下:"<

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

x[i]=0;

knapsack(n,C,w,v,V);

cout<<" ";

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

cout<

cout<

for(i=0;i<=n;i++)

{

cout<

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

{

cout<

}

cout<

cout<

}

cout<<"选择的物向量表示为:";

cout<<" ( ";

traceback(n,C,w,x,V);

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

cout<

cout<<")"<

cout<<"背包最大价值为:"<

cout<

cout<<"按Y或y继续操作,否则按任意键"<

cin>>ch;

if(ch=='Y'||ch=='y')

continue;

else

break;

}

}

动态规划与回溯法解决0-1背包问题

0-1背包动态规划解决问题 一、问题描述: 有n个物品,它们有各自的重量和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 二、总体思路: 根据动态规划解题步骤(问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成)找出01背包问题的最优解以及解组成,然后编写代码实现。 原理: 动态规划与分治法类似,都是把大问题拆分成小问题,通过寻找大问题与小问题的递推关系,解决一个个小问题,最终达到解决原问题的效果。但不同的是,分治法在子问题和子子问题等上被重复计算了很多次,而动态规划则具有记忆性,通过填写表把所有已经解决的子问题答案纪录下来,在新问题里需要用到的子问题可以直接提取,避免了重复计算,从而节约了时间,所以在问题满足最优性原理之后,用动态规划解决问题的核心就在于填表,表填写完毕,最优解也就找到。 过程: a) 把背包问题抽象化(X1,X2,…,Xn,其中 Xi 取0或1,表示第i个物品选或不选),V i表示第i个物品的价值,W i表示第i个物品的体积(重量); b) 建立模型,即求max(V1X1+V2X2+…+VnXn); c) 约束条件,W1X1+W2X2+…+WnXn (V2X2+V3X3+…+VnXn)+V1X1;

最长公共子序列问题(最)

算法作业: LCS 问 题 作业要求:设计一个算法求出两个序列的所有LCS ,分析最坏情况,用“会计方法”证明利用b[i][j]求出 所有LCS 的算法在最坏情况下时间复杂度为)(m m n C O + 1、 算法思路: 根据最长公共子序列问题的性质,即经过分解后的子问题具有高度重复性,并且具有最优子结构性质,采用动态规划法求解问题。设X={x 1, x 2, … , x n }, Y={y 1, y 2, … , y m }, 首先引入二维数组C[i][j]记录X i 和Y j 的LCS 的长度,定义C[i][j]如下: { j i j y i 且x ,i,j ]][j C[i j y i x j i j i C j i C j i C 00001110,]},1][[],][1[max{]][[===>+--≠>--=或,且 为了构造出LCS ,还需要使用一个二维数组b[m][n],b[i][j]记录C[i][j]是通过哪个子问题的值求得 的,以决定搜索的方向,欲求出所有的LCS ,定义数组b 如下: 设1-对角线方向;2-向上;3-向左;4-向上或向左 若X[i]=Y[j],b[i][j] = 1, 若C[i-1][j][i][j-1], 则b[i][j] = 3, 若C[i-1][j]=[i][j-1], 则b[i][j] = 4, 根据以上辅助数组C 和b 的定义,算法首先需要求出这两个数组, C[m][n]中记录的最长公共子序列的长度,b 中记录了查找子序列元素的搜索方向。 利用C 和b 的信息,Find_All_LCS 可以采用回溯法求出所有的LCS 。基本思路如下:使用一个辅助数组记录每次调用Find_All_LCS 得到的LCS 中的元素,每次递归调用一次Find_All_LCS ,进入一个新的执行层,首先要判断当前处理的两个子序列长度是否大于等于0 ,若不满足,则该层的递归结束,返回上一层;然后再判断当前得到的子序列是否等于数组C 中求出的最长公共子序列长度,若等于,则说明算法执行到此已经得到一个LCS ,按序输出;若不等于,此时根据数组b 中记录的搜索方向继续搜索,特别要说明的是,当b[i][j]=4时,即要向上或向左,需要对这两个方向分别调用Find_All_LCS ,保证沿着这两个方向上LCS 元素不被漏掉,都可以搜索到;若b[i][j]=1,即沿对角线方向搜索前进时,此时元素X[i]为LCS 中的元素,存放至辅助数组中去,同时将当前已经求得的LCS 长度增1,当递归调用Find_All_LCS 从b[i][j]=1处时,需要回溯一步,搜索其它路径上可能为LCS 中的元素。当所有的可能路径都已经搜索完,算法结束。 对于某些情况会输出重复的LCS ,这是因为算法在沿不同路径搜索时可能会出现相同的LCS 序列。 2、 时间复杂度分析 由上述对Find_All_LCS 算法的分析可知,求出所有的LCS 实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此,除求解辅助数组C 和b 所用的O(mn+m+n)的执行时间外,Find_All_LCS 的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的情况下,即m=n 并且b 中所有的值都指示沿着对角线方向搜索,时间复杂度为O(n). 相反,当X 和Y 序列不存在公共子序列时为算法的最坏情况,此时C 中所有值都等于0,数组b 中所有的值都指示要分别沿两个不同的方向(向左或向上)搜索,这种情况下每处理一次X[i],Y[j]时总是要沿两个方向分别调用Find_All_LCS ,遇到i=0或j=0时返回,直到搜索完所有的可能路径才结束,最坏情况下的搜索矩阵如下图所示:

最长公共子序列(LCS)问题

程序员编程艺术第十一章:最长公共子序列(LCS)问题 0、前言 程序员编程艺术系列重新开始创作了(前十章,请参考程序员编程艺术第一~十章集锦与总结)。回顾之前的前十章,有些代码是值得商榷的,因当时的代码只顾阐述算法的原理或思想,所以,很多的与代码规范相关的问题都未能做到完美。日后,会着力修善之。 搜遍网上,讲解这个LCS问题的文章不计其数,但大多给读者一种并不友好的感觉,稍感晦涩,且代码也不够清晰。本文力图避免此些情况。力保通俗,阐述详尽。同时,经典算法研究系列的第三章(三、dynamic programming)写的极其糟糕,所以,也算是对那文的一种弥补。有任何问题,欢迎不吝赐教。 第一节、问题描述 什么是最长公共子序列呢?好比一个数列S,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中最长的,则S称为已知序列的最长公共子序列。 举个例子,如:有两条随机序列,如1 3 4 5 5 ,and 2 4 5 5 7 6,则它们的最长公共子序列便是:4 5 5。 第二节、LCS问题的解决思路 ?穷举法 解最长公共子序列问题时最容易想到的算法是穷举搜索法,即对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列,因此,X共有2m个不同子序列(Y亦如此,如为2^n),从而穷举搜索法需要指数时间(2^m * 2^n)。 ?动态规划算法 事实上,最长公共子序列问题也有最优子结构性质。 记: Xi=﹤x1,?,xi﹥即X序列的前i个字符(1≤i≤m)(前缀) Yj=﹤y1,?,yj﹥即Y序列的前j个字符(1≤j≤n)(前缀) 假定Z=﹤z1,?,zk﹥∈LCS(X , Y)。

求最长子序列的长度

一,最长递增子序列问题的描述 设L=是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=,其中k1是对序列L=按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。 最长公共子序列问题用动态规划的算法可解。设Li=< a1,a2,…,a i>,Xj=< b1,b2,…,b j>,它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。则有如下的递推方程: 这可以用时间复杂度为O(n2)的算法求解,由于这个算法上课时讲过,所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n2)的时间,算法的最坏时间复杂度为O(nlogn)+O(n2)=O(n2)。 三,第二种算法:动态规划法 设f(i)表示L中以a i为末元素的最长递增子序列的长度。则有如下的递推方程: 这个递推方程的意思是,在求以a i为末元素的最长递增子序列时,找到所有序号在L前面且小于a i的元素a j,即j

(完整word版)最长公共子序列长度算法

// KSY.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include using namespace std; void LCSLength(int m,int n,char *x ,char *y, int **c, int **b) { int i ,j; for (i = 1; i <= m; i++) c[i][0] = 0; for (i = 1; i <= n; i++) c[0][i] = 0; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) {

if (x[i]==y[j]) { 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; } } } void LCS(int i ,int j, char *x ,int **b) { if (i ==0 || j==0) return; if (b[i][j]== 1) { LCS(i-1,j-1,x,b); printf("%c",x[i]); } else if (b[i][j]== 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); } const int M = 6; const int N = 5; void output(char *s,int n); void LCSLength(int m,int n,char *x,char *y,int * *c,int * *b); void LCS(int i,int j,char *x,int * *b); void main() { char x[] = {' ','B','C','E','F','G','T'}; char y[] = {' ','C','D','F','J','G'}; int **c = new int *[M+1]; int **b = new int *[M+1]; for(int i=0;i<=M;i++) { c[i] = new int[N+1]; b[i] = new int[N+1]; } cout<<"序列X:"<

01背包问题动态规划详解

动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 比如01背包问题。 因为背包最大容量M未知。所以,我们的程序要从1到M一个一个的试。比如,开始任选N件物品的一个。看对应M的背包,能不能放进去,如果能放进去,并且还有多的空间,则,多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢?看下表。 测试数据: 10,3 3,4 4,5 5,6 c[i][j]数组保存了1,2,3号物品依次选择后的最大价值. 这个最大价值是怎么得来的呢?从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为 4,5,6,....10的时候,最佳方案都是放4.假如1号物品放入背包.则再看2号物品.当背包容量为3的时候,最佳方案还是上一排的最价方案c为4.而背包容量为5的时候,则最佳方案为自己的重量5.背包容量为7的时候,很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。 总的最佳方案是5+4为9.这样.一排一排推下去。最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.) 从以上最大价值的构造过程中可以看出。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}这就是书本上写的动态规划方程.这回清楚了吗?

下面是实际程序: #include int c[10][100]; int knapsack(int m,int n) { int i,j,w[10],p[10]; for(i=1;ic[i-1][j]) c[i][j]=p[i]+c[i-1][j-w[i]]; else c[i][j]=c[i-1][j]; }

最长公共子序列实验报告

河北地质大学课程设计报告 (学院)系: 信息工程学院 专业: 计算机科学与技术 姓名: 李义 班级: 二班 学号: 515109030227 指导教师: 王培崇 2016年11月26 日

算法课程设计报告 姓名李义学号515109030227 日期2016/11/10-2016/12/1 实验室152 指导教师王培崇设备编号08 设计题目求最长公共子序列 一、设计内容 求最长公共子序列,如输入字符串str1=adadsda,str2=sadasfda。 则求出的最长公共子序列是adasda。 二、设计目的 掌握动态规划思想,对使用求最长公共子序列加深理解。 三、设计过程 1.算法设计 1. for i ←0 to n 2. L[i,0] ←0 3. end for 4. for j ←0 to m 5. L[0,j] ←0 6. end for 7. for i ←1 to n 8. for j ←1 to m 9. if ai=bj then L[i,j]←L[i-1,j-1]+1 10. else L[i,j]←max {L[i,j-1], L[i-1,j] } 11. end if 12. end for 13. end for 14. return L[n,m] 2.流程图

开始结束 输入I=0,j=0 i<=n L[I,0]=0 i++ Y L[0,j]=0 N j<=n j++ Y i=1 to n J=1 to m ai=bj L[i,j]=L[i-1,j-1]+1 L[i,j]=max{L[i-1,j ],L[i,j-1]} Y J++i++ N 图1.Lcs 算法 3.数据结构 str1=adadsda str2=sadasfda 四、程序实现及运行结果

动态规划之01背包问题(最易理解的讲解)

01背包问题,是用来介绍动态规划算法最经典的例子,网上关于01背包问题的讲解也很多,我写这篇文章力争做到用最简单的方式,最少的公式把01背包问题讲解透彻。 01背包的状态转换方程f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] } f[i,j]表示在前i件物品中选择若干件放在承重为j 的背包中,可以取得的最大价值。 Pi表示第i件物品的价值。 决策:为了背包中物品总价值最大化,第i件物品应该放入背包中吗? 题目描述: 有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,如何让背包里装入的物品具有最 首先要明确这张表是从右到左,至底向上生成的。 为了叙述方便,用e10单元格表示e行10列的单元格,这个单元格的意义是用来表示只有物品e时,有个承重为10的背包,那么这个背包的最大价值是6,因为e物品的重量是4,背包装的了,把e装进去后价值为6。然后是e9单元格表示背包承重9,只有物品e, e装进去后,背包价值为6,接着是e8, e7单元格,一直到e3单元格表示背包承重3,但物品e承重4,装不了,所以e3=0, 对于d10单元格,表示只有物品e,d时,承重为10的背包,所能装入的最大价值,是10,因为物品e,d这个背包都能装进去。对于承重为9的背包,d9=10,是怎么得出的呢? 根据01背包的状态转换方程,需要考察两个值, 一个是f[i-1,j],对于这个例子来说就是e9的值6,另一个是f[i-1,j-Wi]+Pi; 在这里, f[i-1,j]表示我有一个承重为9的背包,当只有物品e可选时,这个背包能装入的最大价值 f[i-1,j-Wi]表示我有一个承重为4的背包(等于当前背包承重减去物品d的重量),当只有物品e可选时,这个背包能装入的最大价值 f[i-1,j-Wi]就是指单元格e4值为6,Pi指的是d物品的价值,即4 由于f[i-1,j-Wi]+Pi = 6 + 4 = 10 大于f[i-1,j] = 6,所以物品d应该放入承重为9的背包,所以d9=10.

动态规划解最长公共子序列问题

动态规划解最长公共子序列问题 动态规划主要针对最优化问题,它的决策是全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随机引起状态的转移.一个决策序列就是在变化的状态中产生出来的,故有”动态”的含义.所以,这种多阶段最优化决策解决问题的过程称为动态规划. 一问题的描述与分析 字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干字符(可能一个也不去掉)后形成的字符序列..令给定的字符序列X=”x0,x1,x2,…xm-1”,序列Y=”y0,y1,…yk-1”是X的子序列,存在X的一个严格递增下标序列i=i0,i1,i2,…ik-1,使得对所有的j=0,1,2,…k-1,有xi=yi。例如X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。 给定两个序列A和B,称序列Z是A和B公共子序列,是指Z同是A和B的子序列。求最长公共子序列。 若A的长度为m,B的长度为n,则A的子序列有2*m-1个,B的子序列有2*n-1个。采用枚举法分别对A和B的所以子序列一一检查,最终求出最长公共子序列。如此比较次数(2*2n)接近指数阶,当n较大时,算法太耗时,不可取。所以要全面考虑不同的情况分别进行决策,,最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后,会不断决策出新的数据,直到找到最优解。 二、算法设计(或算法步骤) A=”a0,a1,a2,……am-1”,B=”b0,b1,b2,……bn-1”,且Z=”z0,z1,z2……zk-1”,为她们的最长公共子序列。不难证明有一下结论: (1)如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,z2,……zk-2”是“a0,a1,a2,…… am-2”和“b0,b1,b2,……bn-2”的一个最长公共子序列; (2)如果am-1!=bn-1,则若zk-1!=am-1,则“z0,z1,z2,……zk-1”是“a0,a1,a2,…… am-2”和”b0,b1,b2,……bn-1”的一个最长公共子序列。 (3)如果am-1!=bn-1,则若zk-1!=bn-1,则“z0,z1,z2,……zk-1”是“a0,a1,a2,…… am-1”和“b0,b1,b2,……bn-2”的一个最长公共子序列。 如此找到了原问题与其子问题的递归关系。 基本存储结构是存储两个字符串及其最长公共子序列的3个一位数组。当然要找出最长公共子序列,要存储当前最长公共子序列的长度和当前公共子序列的长度,而若只存储当前信息,最后只能求解最长公共子序列的长度,却不能找到最长公共子序列本身。因此需建立一个(n+1)*(m+1)的二维数组c,c[i][j]存储序列“a0,a1,a2……ai-2”和“b0,b1,……bj-1”的最长公共子序列长度,由上递推关系分析,计算c[i][j]可递归的表述如下: (1)c[i][j]=0 如果i=0或j=0;

最长公共子序列问题

2.3最长公共子序列问题 和前面讲的有所区别,这个问题的不涉及走向。很经典的动态规划问题。 例题16 最长公共子序列 (lcs.pas/c/cpp) 【问题描述】 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X= < x1, x2,…, xm>,则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列< i1, i2,…, ik>,使得对于所有j=1,2,…,k有Xij=Zj 例如,序列Z=是序列X=的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X 和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>,则序列是X和Y的一个公共子序列,序列也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。 给定两个序列X= < x1, x2, …, xm>和Y= < y1, y2, … , yn>,要求找出X和Y的一个最长公共子序列。 【输入文件】 输入文件共有两行,每行为一个由大写字母构成的长度不超过200的字符串,表示序列X和Y。 【输出文件】 输出文件第一行为一个非负整数,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出文件仅有一行输出一个整数0,否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示。 【输入样例】 ABCBDAB BDCBA 【输出样例】 4 BCBA 【问题分析】 这个问题也是相当经典的。。 这个题目的阶段很不明显,所以初看这个题目没什么头绪,不像前面讲的有很明显的上一步,上一层之类的东西,只是两个字符串而且互相没什么关联。 但仔细分析发现还是有入手点的: 既然说是动态规划,那我们首先要考虑的就是怎么划分子问题,一般对于前面讲到的街道问题和数塔问题涉及走向的,考虑子问题时当然是想上一步是什么?但这个问题没有涉及走向,也没有所谓的上一步,该怎么办呢? 既然是求公共子序列,也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。 那么我们枚第一个序列(X)的字符,和第二个序列(Y)的字符。 显然如果X[i]=Y[j]那么起点是1(下面说的子序列都是起点为1的),长度为i的子序列和长度为j的子序列的最长公共子序列就是长度为i-1和长度为j-1 的子序列中最长的公共子

算法分析与程序设计动态规划及回溯法解背包问题

动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会 有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。 多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理(最优子结构性质)最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2……Wn,与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目 标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。

最长公共子序列问题

实验三最长公共子序列问题 1.实验环境 本实验采用 java 语言编写实现,环境:,编译器: eclipse 2.实验目的 通过最长公共子序列问题,巩固并详细分析动态规划思想和解题 步骤。 3.设计思路 最长公共子序列的定义为:设有两个序列S[1..m]和9[仁n],需要寻找它们之间的一个最长公共子序列。 例如,假定有两个序列: S1: I N T H E B E G I N N I N G S2: A L L T H I N G S A R E L O S T 则S i和S的一个最长公共子序列为 THING又比如: S1: A B C B D A B S2: B D C A B A 则它们的一个最长公共子序列为 BCBA。 这里需要注意的是,一个子序列不一定必须是连续的,即中间可被其他字符分开,单它们的顺序必须是正确的。另外,最长公共子序列不一定只有一个,而我们需要寻找的是其中一个。

当然,如果要求子序列里面的元素必须连成一片也是可以的。实际上,连成一片的版本比这里实现的更容易。 4.过程 我们可以通过蛮力策略解决这个问题,步骤如下: 1.检查S1[1..m]里面每一个子序列。 2.看看其是否也是S2[1..n]里的子序列。 3.在每一步记录当前找到的子序列里面最长的子序列。 这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。 利用动态规划寻找最长公共子序列步骤如下: 1.寻找最长公共子序列的长度。 2.扩展寻找长度的算法来获取最长公共子序列。 策略:考虑序列S1和S2的前缀序列。 设 c[i,j] = |LCS (S1[1..i],S2[1..j]),则有 c[m, n] = |LCS(S1 S2)| 所以有 c[ i -1 , j -1 ] + 1, 如要 S1[i] = S2[j] c[i, j]= max{ c [ i - 1, j ], c[ i , j -1 ] }, 如果 S1[i]工S2[j] 然后回溯输出最长公共子序列过程:

01背包问题动态规划详解及C++代码

0/1背包问题动态规划详解及C++代码 1. 问题描述 给定一个载重量为C的背包 有n个物品 其重量为wi 价值为vi 1<=i<=n 要求:把物品装入背包 并使包内物品价值最大2. 问题分析 在0/1背包问题中 物体或者被装入背包 或者不被装入背包 只有两种选择。循环变量i j意义 前i个物品能够装入载重量为j的背包中 数组c意义 c[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值 若w[i]>j 第i个物品不装入背包 否则 若w[i]<=j且第i个物品装入背包后的价值>c[i-1][j] 则记录当前最大价值 替换为第i个物品装入背包后的价值 其c++代码如下 #include using namespace std; void KANPSACK_DP(int c[50][50], int w[50], int v[50], int n, int C) { for(int i = 0; i <= C; i ++) { c[0][i] = 0; } for(int i = 1; i <= n; i ++) { c[i][0] = 0; for(int j = 1; j <= C; j ++) { if(w[i] <= j) { if(v[i] + c[i - 1][j - w[i]] > c[i - 1][j]) c[i][j] = v[i] + c[i - 1][j - w[i]]; else c[i][j] = c[i - 1][j]; } else c[i][j] = c[i - 1][j]; } } } void OUTPUT_SACK(int c[50][50], int x[50], int w[50], int n, int C) { for(int k = n; k >= 2; k --) { if(c[k][C] == c[k-1][C]) x[k] = 0; else { x[k] = 1; C = C - w[k];

最长公共子序列实验报告

最长公共子序列问题 一.实验目的: 1.加深对最长公共子序列问题算法的理解,实现最长公共子序列问题的求解算法; 2.通过本次试验掌握将算法转换为上机操作; 3.加深对动态规划思想的理解,并利用其解决生活中的问题。 二.实验内容: 1.编写算法:实现两个字符串的最长公共子序列的求解; 2.将输入与输出数据保存在文件之中,包括运行时间和运行结果; 3.对实验结果进行分析。 三.实验操作: 1.最长公共子序列求解: 将两个字符串放到两个字符型数组中,characterString1和characterString2,当characterString1[m]= characterString2[m]时,找出这两个字符串m之前的最长公共子序列,然后在其尾部加上characterString1[m],即可得到最长公共子序列。当characterString1[m] ≠characterString2[m]时,需要解决两个子问题:即找出characterString1(m-1)和characterString2的一个最长公共子序列及characterString1和characterString2(m-1)的一个最长公共子序列,这两个公共子序列中较长者即为characterString1和characterString2的一个最长公共子序列。 2.动态规划算法的思想求解: 动态规划算法是自底向上的计算最优值。 计算最长公共子序列长度的动态规划算法LCS-Length以characterString1和characterString2作为输入,输出两个数组result和judge1,其中result存储最长公共子序列的长度,judge1记录指示result的值是由那个子问题解答得到的,最后将最终的最长公共子序列的长度记录到result中。 以LCS-Length计算得到的数组judge1可用于快速构造序列最长公共子序列。首先从judge1的最后开始,对judge1进行配对。当遇到“↖”时,表示最长公共子序列是由characterString1(i-1)和characterString2(j-1)的最长公共子序列在尾部加上characterString1(i)得到的子序列;当遇到“↑”时,表示最长公共子序列和characterString1(i-1)与characterString2(j)的最长公共子序列相同;当遇到“←”时,表示最长公共子序列和characterString1(i)与characterString2(j-1)的最长公共子序列相同。 如图所示:

最长公共子序列问题LCS-Read

最长公共子序列问题LCS 问题描述 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X=,则另一序列Z=是X的子序列是指存在一个严格递增的下标序列,使得对于所有j=1,2,…,k有 例如,序列Z=是序列X=的子序列,相应的递增下标序列为<2,3,5,7>。 给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X=和Y=,则序列是X和Y的一个公共子序列,序列也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。 最长公共子序列(LCS)问题:给定两个序列X=和Y=,要求找出X和Y的一个最长公共子序列。 参考解答 动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。 1.最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法,即对X的每一个子序列,检查它是否也是Y的子序列,从而确定它是否为X和Y的公共子序列,并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X 的一个子序列相应于下标序列{1, 2, …, m}的一个子序列,因此,X共有2m个不同子序列,从而穷举搜索法需要指数时间。 事实上,最长公共子序列问题也有最优子结构性质,因为我们有如下定理: 定理: LCS的最优子结构性质 设序列X=和Y=的一个最长公共子序列Z=,则: 1.若x m=y n,则z k=x m=y n且Z k-1是X m-1和Y n-1的最长公共子序列; 2.若x m≠y n且z k≠x m ,则Z是X m-1和Y的最长公共子序列;

0-1背包问题动态规划详解及代码

0/1 背包问题动态规划详解及C代码 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结果。然后利用这些结果减轻运算量。 问题描述: 给定N中物品和一个背包。物品i的重量是W i,其价值位V i,背包的容量为C。问应该如何选择装入背包的物品,使得转入背包的物品的总价值为最大?? 在选择物品的时候,对每种物品i只有两种选择,即装入背包或不装入背包。不能讲物品i 装入多次,也不能只装入物品的一部分。因此,该问题被称为0-1背包问题。 问题分析:令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) jw 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的背包中的最优解。 比如01背包问题。 因为背包最大容量M未知。所以,我们的程序要从1到M一个一个的试。比如,开始任选N件物品的一个。看对应M的背包,能不能放进去,如果能放进去,并且还有多的空间,则,多出来的空间里能放N-1物品中的最大价值。怎么能保证总选择是最大价值呢?看下表。测试数据: 10,3 3,4 4,5 5,6

最长公共子序列问题

实验三最长公共子序列问题 1. 实验环境 本实验采用java 语言编写实现,环境:,编译器:eclipse 2. 实验目的 通过最长公共子序列问题,巩固并详细分析动态规划思想和解题步骤。 最长公共子序列的定义为:设有两个序列S i[1..m]和84仁n],需要寻找它们之间的一个最长公共子序列。 例如,假定有两个序列: 81:I N T H E B E G I N N I N G 82:A L L T H I N G 8 A R E L O 8 T 则8i和S的一个最长公共子序列为THING又比如: 81:A B C B D A B 82:B D C A B A 则它们的一个最长公共子序列为BCBA。 这里需要注意的是,一个子序列不一定必须是连续的,即中间可被其他字符分开,单它们的顺序必须是正确的。另外,最长公共子序列不一定只有一个,而我们需要寻找的是其中一个。

当然,如果要求子序列里面的元素必须连成一片也是可以的。实 际上,连成一片的版本比这里实现的更容易。 4.过程 我们可以通过蛮力策略解决这个问题,步骤如下: 1. 检查S1[1..m]里面每一个子序列。 2. 看看其是否也是S2[1..n]里的子序列。 3. 在每一步记录当前找到的子序列里面最长的子序列。 这种方法的效率十分低下。因此本实验采用动态规划的方法实现 该算法。 利用动态规划寻找最长公共子序列步骤如下: 1.寻找最长公共子序列的长度。 2.扩展寻找长度的算法来获取最长公共子序列。 策略:考虑序列S1和S2的前缀序列。 设 c[i ,j] = |LCS (S1[1..i],S2[1..j]),则有 c[m , n] = |LCS(S1 S2)| 所以有 c[i ,j]= max{ c [ i - 1, j ], c[ i , j -1 ] }, c[ i -1 , j -1 ] + 1, 如要 S1[i] = S2[j] 如果 S1[i]工 S2[j]

动态规划法求解最长公共子序列(含Java代码)

公共子序列问题徐康123183 一.算法设计 假设有两个序列X和Y,假设X和Y分别有m和n个元素,则建立一个二维数组C[(m+1)*(n+1)],记录X i与Y j的LCS的长度。将C[i,j]分为三种情况: 若i =0 或j =0时,C[i,j]=0; 若i,j>0且X[i]=Y[j],C[i,j]=C[i-1,j-1]+1; 若i,j>0且X[i] Y[j],C[i,j]=max{C[i-1,j],C[i,j-1]}。 再使用一个m*n的二维数组b,b[i,j]记录C[i,j]的来向: 若X[i]=Y[j],则B[i,j]中记入“↖”,记此时b[i,j] = 1; 若X[i] Y[j]且C[i-1,j] > C[i,j-1],则b[i,j]中记入“↑”,记此时B[i,j] = 2; 若X[i] Y[j]且C[i-1,j] < C[i,j-1],则b[i,j]中记入“←”,记此时B[i,j] = 3; 若X[i]Y[j]且C[i-1,j] = C[i,j-1],则b[i,j]中记入“↑”或“←”,记此时B[i,j] = 4; 得到了两个数组C[]和B[],设计递归输出LCS(X,Y)的算法: LCS_Output(Direction[][], X[], i, j, len,LCS[]){ If i=0 or j=0 将LCS[]保存至集合LCS_SET中 then return; If b[i,j]=1 then /*X[i]=Y[j]*/ {LCS_Output(b,X,i-1,j-1); 将X[i]保存至LCS[len-i];} else if b[i,j]=2 then /*X[i]Y[j]且C[i-1,j]>C[i,j-1]*/ LCS_Output(b,X,i-1,j) else if b[i,j]=3 then /*X[i]Y[j]且C[i-1,j]

相关主题