算法分析之动态规划

算法分析之动态规划nullnull实验要求实验要求理解动态规划的原理及一般应用最优子结构子问题重叠递归关系的提取编程实现典型的动态规划算法，对算法进行验证，分析算法复杂度。实验内容实验内容1 Edit-Distance 字符串A通过插入、删除、替换字符变成另一个字符串B，操作的次数表示两个字符串的差异。用于计算文本相关性、相似性递归关系两字符串长度为N、M，对1≤i≤N，1≤j≤M，有若ai=bj 则LD(i,j)=LD(i-1,j-1) 若ai≠bj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,...

nullnull实验要求实验要求理解动态规划的原理及一般应用最优子结构子问题重叠递归关系的提取编程实现典型的动态规划算法，对算法进行验证，分析算法复杂度。实验内容实验内容1 Edit-Distance 字符串A通过插入、删除、替换字符变成另一个字符串B，操作的次数表示两个字符串的差异。用于计算文本相关性、相似性递归关系两字符串长度为N、M，对1≤i≤N，1≤j≤M，有若ai=bj 则LD(i,j)=LD(i-1,j-1) 若ai≠bj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1实验内容实验内容求解例 A=GGATCGA，B=GAATTCAGTTA，计算LD(A,B) 第一步：初始化LD矩阵实验内容实验内容第二步：利用递归式，依次列出其他行列若ai=bj 则LD(i,j)=LD(i-1,j-1) 若ai≠bj 则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1null实验内容实验内容2 0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。 0-1表示要么装，要么不装。实验内容实验内容分析考虑由前i (1≤i≤n)个物品定义的实例，物品重量分别为w1,w2,…wi，价值分别为v1,v2,…vi，背包承重量 j (1 ≤ j ≤ w)。设V[i,j]为能放进承重量为j的前i个物品中最有价值子集的总价值。这个子集分两类：不包括第i个物品的最优子集价值是v[i-1,j] 包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi + V[ i-1, j-wi ]。实验内容实验内容分析考虑由前i (1≤i≤n)个物品定义的实例，物品重量分别为w1,w2,…wi，价值分别为v1,v2,…vi，背包承重量 j (1 ≤ j ≤ w)。设V[i,j]为能放进承重量为j的前i个物品中最有价值子集的总价值。这个子集分两类：不包括第i个物品的最优子集价值是v[i-1,j] 包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi + V[ i-1, j-wi ]。实验内容实验内容实验结果实验结果按要求粘贴算法名称及代码个人信息适时嵌入代码代码要注意换行、缩进层次要有注释，最好有着色 http://10.2.130.222/code/ 结果截图分析结论报告严格命名学号_姓名_实验3.doc 上传至ftp://10.2.130.222/Upload/Ex3

                    本文档为【算法分析之动态规划】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

算法分析之动态规划

你可能还喜欢