算法分析之动态规划1.ppt_第1页
算法分析之动态规划1.ppt_第2页
算法分析之动态规划1.ppt_第3页
算法分析之动态规划1.ppt_第4页
算法分析之动态规划1.ppt_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、实验3 动态规划,实验要求,理解动态规划的原理及一般应用 最优子结构 子问题重叠 递归关系的提取 编程实现典型的动态规划算法，对算法进行验证，分析算法复杂度。,实验内容,1 Edit-Distance 字符串A通过插入、删除、替换字符变成另一个字符串B，操作的次数表示两个字符串的差异。 用于计算文本相关性、相似性 递归关系 两字符串长度为N、M，对1iN，1jM，有 若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)+1,实验内容,求解例 A=GGATCGA，B=GAATTCAGTTA，计

2、算LD(A,B) 第一步：初始化LD矩阵,实验内容,第二步：利用递归式，依次列出其他行列,若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)+1,实验内容,2 0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。 0-1表示要么装，要么不装。,实验内容,分析 考虑由前i (1in)个物品定义的实例，物品重量分别为w1,w2,wi，价值分别为v1,v2,v

3、i，背包承重量 j (1 j w)。 设Vi,j为能放进承重量为j的前i个物品中最有价值子集的总价值。这个子集分两类： 不包括第i个物品的最优子集价值是vi-1,j 包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi + V i-1, j-wi 。,实验内容,分析 考虑由前i (1in)个物品定义的实例，物品重量分别为w1,w2,wi，价值分别为v1,v2,vi，背包承重量 j (1 j w)。 设Vi,j为能放进承重量为j的前i个物品中最有价值子集的总价值。这个子集分两类： 不包括第i个物品的最优子集价值是vi-1,j 包括第i个物品的子集中，该最优子集是由该物品和前i-1个物品中能放进承重j-wi的背包的最优子集组成，总价值为vi + V i-1, j-wi 。,实验内容,实验结果,按要求粘贴 算法名称及代码 个人信息适时嵌入代码 代码要注意换行、缩进层次 要有注释，最好有着色 22/code/ 结果截图 分析结

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论