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

一些动态规划习题及解答

自己找的一些动规的习题。

例13-4迷宫寻宝【问题描述】

一个n行m列的迷宫(1<=n,m<=5),入口在左上角,规定只能向下或向右走。迷宫的某些地方藏有不同价值(>0)的宝藏,同时又存在一些障碍无法通过。求到达右下角出口时收集宝藏的最大值。

【输入】

第一行n和m

一下n行m

一些动态规划习题及解答

【输出】

最大值

【样例输入】34

2-1505

13-16-18910

【样例输出】33

【分析】

a[I,j]保存第i行第j列的宝藏价值。

令f[i,j]为从(1,1)走到第i行第j列时所能收集的宝藏的最大价值。状态转移方程:

f[i,j]=max{f[i-1,j],f[i,j-1]}+a[i,j](i<=n,1<=m)条件:n[i,j]<>-1初始:f[1,1]=a[1,1]目标:f[n,m]【参考程序】

constmaxn=50;maxm=50;fin=’b1.in’;fout=’b1.out’;var

f,a:array[0..maxn+1,0..maxm+1]ofinteger;I,j,k,n,m,t:integer;procedureinit;begin

assign(input,fin);reset(input);readln(n,m);

fori:=0ton+1do

forj:=0tom+1doa[i,j]:=-1;a[0,1]:=0;

fori:=1tondoforj:=1tomdobegin

read(a[i,j]);

if(a[i,j-1]=-1)and(a[i-1,j]=-1)thena[i,j]:=-1;//很关键的预处理end;

close(input);end;

functionmax(a,b:integer):integer;

第1页

你可能喜欢

  • 网络最大流问题
  • 动态规划经典
  • C语言经典算法
  • 规划总结
  • 考研数学模拟题
  • 动态规划的优化
  • 算法合集
  • 动态规划算法

热门文档

相关文档

  • 动态规划习题分析

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

  • 动态规划练习题(含答案)

    动态规划练习题(含答案)_理学_高等教育_教育专区。最正规版动态规划练习题(含...(); return 0; } USACO 2.3 Longest Prefix 题目如下: 在生物学中,一些...

  • 动态规划习题答案

    动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案2.某公司有资金 4 百万元向 A,B 和 C...

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

    一些动态规划习题及解答 28页 3下载券 第6章 动态规划-习题6.1 暂无评价 ...动态规划练习题 [题 1] 多米诺骨牌(DOMINO) 问题描述:有一种多米诺骨牌是平面...

  • 动态规划讲解大全(含例题及答案)

    动态规划讲解大全(含例题及答案)_IT认证_资格考试/认证_教育专区。最全面、最...虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关...

  • 动态规划习题

    特别是对于离散的问题,由于解析数学无法发挥作用,动态规划便成为了一种非常 有用...1.2 动态规划的基本概念 动态规划的数学描述离不开它的一些基本概念与符号,...

  • 动态规划习题及参考答案

    动态规划习题及参考答案_理学_高等教育_教育专区。动态规划习题及参考答案2010 第六章动态规划书面作业参考答案 2010 第六章动态规划书面作业参考答案 一、 (1)P...

  • 第六章 动态规划习题课

    第3章-动态规划-习题 20页 1下载券 一些动态规划习题及解答 28页 3下载券...§6 动态规划应用举例 1 资源分配问题 2 生产与存储问题 3 排序问题 4 设备...

  • 动态规划例题

    动态规划例题版本20071002 版本 清华大学 刘汝佳 HandsShaking ? n<=50个人坐在...你有一些Fence,但是其中一些破了。你希 望修复它们。每次可以修复一个区间[i,...

  • 动态规划习题

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

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