好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

第3章 算法习题.doc

4页
  • 卖家[上传人]:ni****g
  • 文档编号:539131195
  • 上传时间:2023-07-16
  • 文档格式:DOC
  • 文档大小:59.01KB
  • / 4 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 第三章 动态规划算法分析题 3-1 最长单调递增子序列设计一个时间的算法,找出由n个数组成的序列的最长单调递增子序列分析与解答:由数组b[0:n-1]记录以a[i], 0<=itemp) temp=b[i];return temp;}算法LISdyna按照递归式计算出b[0: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背包问题问题的形式化描述是:给定c>0,d>0,wi>0,bi>0,vi>0,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)的递归式如下:按此递归式计算出的m(n,c,d)为最优值算法所需的计算时间为O(ncd)。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.