动态规划习题及参考答案
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个工程获得的最大价值。
动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的... 动态规划习题及参考答案 5页 1下载券 5 动态规划算法习题答案 9页 2下载券...
动态规划习题及参考答案 5页 1下载券 第3章-动态规划-习题 17页 1下载券 ...? ? xi ? 0, (i ? 1,2,3) 应用动态规划求解: 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 ...
动态规划习题及参考答案 5页 1财富值 动态规划习题分析 31页 2财富值喜欢此文档的还喜欢 第3章-动态规划-复习 47页 5财富值 0-1背包问题动态规划详解及.....
习题答案选03_整数规划 4页 免费 动态规划习题及参考答案 5页 1财富值 一些... 胡运权 运筹学教程 课后习题答案胡运权 运筹学教程 课后习题答案隐藏>> 运筹...
动态规划习题动态规划习题隐藏>> 动态规划专题分类视图 数轴动规题: 数轴动规题: ... 1 较复杂的数轴动规 ... 4 线性动规 ......
热门文档