青青子衿abc 2022-05-21 12:50 采纳率: 50%
浏览 197
已结题

动态规划问题,请大家看一下

两台月球矿车从A点向B点移动探测,每台矿车每次可以向右或向下移动一步,移动到的位置对应的数据为可采集的矿石数量 假设每台矿车矿石装载量无限,请求出两台矿车都到达B点后采集到的矿石数量总和最大值,并将他们经过的路径输出 动态规划问题
算法思想 代码和伪代码 复杂度(空间和时间)

img

可以当作一辆车,第一辆车先走,采集过的置为0,然后第2辆车再走.这种贪心策略是错误的

img


如上图所示,通过观察可以发现,该图的最优值应该为(3+2)+(1+3)=9
但如果按照上述思路,第一台矿车采矿值应为3+3+0=6,之后把图中第二行第一列和第2行第2列的2个3全部清零,之后第二台矿车再走,能够采矿数最多只有2,这时得到的解为6+2=8,不是全局最优解

  • 写回答

5条回答 默认 最新

  • 真相重于对错 2022-05-21 18:52
    关注

    用两个状态数组

    评论

报告相同问题?

问题事件

  • 系统已结题 5月29日
  • 赞助了问题酬金20元 5月21日
  • 创建了问题 5月21日

悬赏问题

  • ¥15 基于卷积神经网络的声纹识别
  • ¥15 Python中的request,如何使用ssr节点,通过代理requests网页。本人在泰国,需要用大陆ip才能玩网页游戏,合法合规。
  • ¥100 为什么这个恒流源电路不能恒流?
  • ¥15 有偿求跨组件数据流路径图
  • ¥15 写一个方法checkPerson,入参实体类Person,出参布尔值
  • ¥15 我想咨询一下路面纹理三维点云数据处理的一些问题,上传的坐标文件里是怎么对无序点进行编号的,以及xy坐标在处理的时候是进行整体模型分片处理的吗
  • ¥15 CSAPPattacklab
  • ¥15 一直显示正在等待HID—ISP
  • ¥15 Python turtle 画图
  • ¥15 stm32开发clion时遇到的编译问题