第3章 算法习题.doc_第1页
第3章 算法习题.doc_第2页
第3章 算法习题.doc_第3页
第3章 算法习题.doc_第4页
全文预览已结束

下载本文档

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

文档简介

第三章 动态规划算法分析题 3-1 最长单调递增子序列设计一个时间的算法，找出由n个数组成的序列的最长单调递增子序列。分析与解答：由数组b0:n-1记录以ai, 0=in，为结尾元素的最长递增子序列的长度。序列a的最长递增子序列的长度为。易知，bi满足最优子结构性质，可以递归的定义为：b0=1,将此计算bi转化为i个规模更小的子问题。按此思想设计的动态规划算法描述如下。int LISdyna()int i, j, k;for (i=1,b0=1;in;i+) for (j=0,k=0;jI;j+) if (aj=ai & kbj) k=bj; bi=k-1;Return maxL(n); int maxL(int n)for (int=0, temp=0; itemp) temp=bi;return temp;算法LISdyna按照递归式计算出b0:n-1的值，然后由maxL计算出序列a的最长递归子序列的长度。从算法LISdyna的二重循环容易看出，算法所需的计算时间为。算法分析题3-3 整数线性规划问题分析与解答：该问题是一般情况下的背包问题。具有最优子结构性质。设所给背包问题的子问题的最优解为m（i,j），即m（i,j）是背包容量为j，可选择物品为1，2，i时背包问题的最优值。由背包问题的最优子结构性质，可以建立计算m（i,j）的递归式如下：按此递归式计算出的m(n,b)为最优值。算法所需的计算时间。算法分析题3-4分析与解答：该问题是二维0-1背包问题。问题的形式化描述是：给定c0,d0,wi0,bi0,vi0,1=i=n，要求找出n元0-1向量,使得而且达到最大。因此，二维0-1背包问题也是一个特殊的整数规划问题。容易证明该问题具有最优子结构性质。设所给二维0-1背包问题的子问题的最优值为m(i,j,k)，即m(i,j,k)是背包容量为j，容积为k，可选择物品为时二维0-1背包问题的最优值。由二维0-1背包问题的最优子结构性质，可以建立计算m(i,j,k)的递
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论