算法分析之动态规划

段旭良四川农业大学段旭良四川农业大学实验要求实验要求n理解动态规划的原理及一般应用n最优子结构最优子结构n子问题重叠子问题重叠n递归关系的提取递归关系的提取n编程实现典型的动态规划算法，对算法进行验证，分析算法复杂度。段旭良四川农业大学段旭良四川农业大学实验内容实验内容n1 Edit-Distancen字符串字符串A通过插入、删除、替换字符变成另一个字通过插入、删除、替换字符变成另一个字符串符串B，操作的次数表示两个字符串的差异。操作的次数表示两个字符串的差异。n用于计算文本相关性、相似性用于计算文本相关性、相似性n递归关系n两字符串长度为两字符串长度为N、M，对对1iN，1jM，有，有n若若ai=bjn则则LD(i,j)=LD(i-1,j-1)n若若aibjn则则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1)+1段旭良四川农业大学段旭良四川农业大学实验内容实验内容n求解例nA=GGATCGA，B=GAATTCAGTTA，计算，计算LD(A,B)n第一步：初始化第一步：初始化LD矩阵矩阵LD算法矩阵 GAATTCAGTTA 0123456789 10 11G10 1 2 3 4 5 6 7 8 9 10 G2 A3 T4 C5 G6 A7 段旭良四川农业大学段旭良四川农业大学实验内容实验内容n第二步：利用递归式，依次列出其他行列第二步：利用递归式，依次列出其他行列若ai=bj则LD(i,j)=LD(i-1,j-1)若aibj则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1)+1LD算法矩阵 GAATTCAGTTA 0123456789 10 11G10123456789 10G211234566789A321123456788T432212345678C543322234567G654433333456A765444434455段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学段旭良四川农业大学实验内容实验内容n2 0-1背包问题n给定给定n种物品和一背包。物品种物品和一背包。物品i的重量是的重量是wi，其价值，其价值为为vi，背包的容量为，背包的容量为C。问应如何选择装入背包的物。问应如何选择装入背包的物品，使得装入背包中物品的品，使得装入背包中物品的总价值最大总价值最大?n0-1背包问题背包问题是一个特殊的整数规划问题。是一个特殊的整数规划问题。n0-1表示要么装，要么不装。表示要么装，要么不装。nixCxwxviniiiniii1,1,0max11段旭良四川农业大学段旭良四川农业大学实验内容实验内容n分析n考虑由前考虑由前i(1in)个物品定义的实例，物品重量分个物品定义的实例，物品重量分别为别为w1,w2,wi，价值分别为，价值分别为v1,v2,vi，背包承重量，背包承重量 j(1 j w)。n设设Vi,j为能放进为能放进承重量为承重量为j的的前前i个物品个物品中最有价值中最有价值子集的子集的总价值总价值。这个子集分两类：。这个子集分两类：n不包括第不包括第i个物品的最优子集价值是个物品的最优子集价值是vi-1,jn包括第包括第i个物品的子集中，该最优子集是由该物品和个物品的子集中，该最优子集是由该物品和前前i-1个物品中能放进承重个物品中能放进承重j-wi的背包的最优子集组成，的背包的最优子集组成，总价值为总价值为vi+V i-1,j-wi。段旭良四川农业大学段旭良四川农业大学实验内容实验内容n分析n考虑由前考虑由前i(1in)个物品定义的实例，物品重量分个物品定义的实例，物品重量分别为别为w1,w2,wi，价值分别为，价值分别为v1,v2,vi，背包承重量，背包承重量 j(1 j w)。n设设Vi,j为能放进承重量为为能放进承重量为j的前的前i个物品中最有价值个物品中最有价值子集的总价值。这个子集分两类：子集的总价值。这个子集分两类：n不包括第不包括第i个物品的最优子集价值是个物品的最优子集价值是vi-1,jn包括第包括第i个物品的子集中，该最优子集是由该物品和个物品的子集中，该最优子集是由该物品和前前i-1个物品中能放进承重个物品中能放进承重j-wi的背包的最优子集组成，的背包的最优子集组成，总价值为总价值为vi+V i-1,j-wi。00,V0i0),0(,00),1(),1(),1(max),(ijVjwjwjjiVvwjiVjiVjiViiii时，；时段旭良四川农业大学段旭良四川农业大学实验内容实验内容物品重量价值1212元2110元3320元4215元承重量承重量ji0123450000000w1=2,v1=1210012121212w2=1,v2=10201012222222w3=3,v3=20301012223032w4=2,v4=154010152530370j-wij W0 i-1V(i-1,j-wi)V(i-1,j)iV(i,j)i+1 n 段旭良四川农业大学段旭良四川农业大学实验结果实验结果n按要求粘贴n算法名称及代码算法名称及代码n个人信息适时嵌入代码个人信息适时嵌入代码n代码要注意换行、缩进层次代码要注意换行、缩进层次n要有注释，最好有着色要有注释，最好有着色nhttp:/10.2.130.222/code/n结果截图结果截图n分析结论分析结论报告严格命名 学号_姓名_实验3.doc 上传至ftp:/10.2.130.222/Upload/Ex3