文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 动态规划习题及参考答案
侵权投诉

动态规划习题及参考答案

动态规划习题及参考答案

2010第六章动态规划书面作业参考答案

一、 (1)P159,4(只计算最长路径),求出原点s到终点t的所有最(长)路径。 解:动态规划函数:

设cost[i]为0到顶点i的最长路径值。 d[i]为cost[i]取极值时i的前一顶点。 递推公式见教案,将min改为max。

初始:cost[0] = 0 计算:

cost[1] = cost[0] + c01 = 4 d[1] = 0

cost[2] = cost[0] + c02 = 5 d[2] = 0

cost[3] = max{cost[0]+c03, cost[1]+c13,cost[2]+c23} = 10 d[3] = 1,2

同理,计算得

cost[4] = 18 d[4] = 3 cost[5] = 19 d[5] = 3 cost[6] = 23 d[6] = 4,5 故0到6的最长路经长度为23。 回溯得路经为:

6 4 3 1 0 6 4 3 2 0 6 5 3 1 0 6 5 3 2 0

二、 设资源份额为m,工程个数为n,分配x份资源给第i个工程获得的利润为Gi(x)。设

计动态规划算法给出最优资源分配方案,即将m份资源分配给n 个工程获得的利润最大。

(1) 写出动态规划函数及其递归表达式。

(2) 写出算法对如下数据的计算过程,给出最大利润及最优分配方案。

m=3,n=3,利润表如下:

动态规划习题及参考答案

解:(1)设动态规划函数fi(x),表示将x份资源分配给前i个工程获得的最大价值。

第1页

你可能喜欢

  • 参考答案
  • 运筹学考试
  • 网络图练习题
  • 最优控制习题
  • 动态规划算法
  • 分支限界法
  • 分治算法

热门文档

相关文档

  • 动态规划习题答案

    动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的... 动态规划习题及参考答案 5页 1下载券 5 动态规划算法习题答案 9页 2下载券...

  • 动态规划习题

    动态规划习题及参考答案 5页 1下载券 第3章-动态规划-习题 17页 1下载券 ...? ? xi ? 0, (i ? 1,2,3) 应用动态规划求解: 1、分阶段:考虑效益...

  • 动态规划练习题及解答1

    动态规划总结(基本类型) 6页 免费 动态规划习题及参考答案 5页 1下载券 ...动态规划练习题 [题 1] 多米诺骨牌(DOMINO) 问题描述:有一种多米诺骨牌是平面...

  • 一些动态规划习题及解答

    动态规划习题 26页 5财富值 动态规划习题及参考答案 5页 1财富值 第3章-... 自己找的一些动规的习题。自己找的一些动规的习题。隐藏>> 例13-4 迷宫...

  • 动态规划习题分析

    一些动态规划习题及解答 28页 3下载券 动态规划习题及参考答案 5页 1下载券...or g 一般步骤 恰当地使用数据可以使动态规划的时间复 杂度降下。 队列——O...

  • 动态规划习题详解

    动态规划习题详解_文学_高等教育_教育专区。动态规划习题动态规划动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种方法. 动态规划是运筹学的一...

  • 动态规划 练习题

    动态规划练习题 23.(11 分) 请用动态规划逆序求解法求解下列问题:求出下图中...(可直接在图上标号,最后给定 答案) B1 2 4 6 3 A 4 B2 2 4 3 7 ...

  • 第3章-动态规划-习题

    动态规划习题及参考答案 5页 1财富值 动态规划习题分析 31页 2财富值喜欢此文档的还喜欢 第3章-动态规划-复习 47页 5财富值 0-1背包问题动态规划详解及.....

  • 习题答案选04_动态规划

    习题答案选03_整数规划 4页 免费 动态规划习题及参考答案 5页 1财富值 一些... 胡运权 运筹学教程 课后习题答案胡运权 运筹学教程 课后习题答案隐藏>> 运筹...

  • 动态规划习题

    动态规划习题动态规划习题隐藏>> 动态规划专题分类视图 数轴动规题: 数轴动规题: ... 1 较复杂的数轴动规 ... 4 线性动规 ......

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email