V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
kidding
V2EX  ›  算法

求助一道算法题,求最便宜路径

  •  2
     
  •   kidding · 2021-10-01 03:16:12 +08:00 · 1078 次点击
    这是一个创建于 910 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问题如下

    你正在玩一款游戏。一共有 n 个镇,现在你在 a 镇并想走到 b 镇。与其他游戏中可以不停地走上几个小时不同,在这个游戏里你不能这样做。你有当前的耐力点数,如果耐力降至 0,则将无法再走下去。

    在相距 d 公里的两个城镇之间的道路上行走会消耗 d 耐力点。如果你目前没有至少 d 耐力点,那么你将不能走这条路。

    每个城镇都有一个旅馆可以休息。每休息一小时,就会恢复 1 点耐力,直至你的最大耐力点 m 。每家旅馆都有不同的每个小时休息价格。

    你不想在旅馆里浪费不必要的钱。请问从起始城镇 a 到目的地城镇 b 最便宜的价格是多少?

    本来以为是最短路径问题,但想了一下如果当前体力不够完全可以绕路去附近比较近的城市休息才可以保证总价格最便宜。甚至有可能附近的城市是死路,但可以过去恢复完耐力再往回走,所以也不能简单地把每个城市的旅馆价格作为权重。

    想了很久也没想出解法,所以发出来问问大家意见。

    5 条回复    2021-10-01 12:24:51 +08:00
    litmxs
        1
    litmxs  
       2021-10-01 03:38:59 +08:00 via Android   ❤️ 1
    动态规划吧,记 dp[i]为从 a 镇到 i 镇最便宜的价格,dp[a]=0,参考 Dijkstra 算法更新 dp 数组
    kidding
        2
    kidding  
    OP
       2021-10-01 03:42:16 +08:00
    @litmxs #1 感谢回复。应该是个 DP 问题,但只算最便宜价格的话没法考虑耐力恢复的问题吧。
    litmxs
        3
    litmxs  
       2021-10-01 03:47:09 +08:00 via Android
    @kidding 应该再加一个维度,dp[i][j]表示到达城镇 i,耐力至少剩余 j 最便宜的价格
    kidding
        4
    kidding  
    OP
       2021-10-01 07:59:57 +08:00
    @litmxs #3 刚才尝试写了一下,但增加维度的话在 dijkstra 算法比较价格的时候又不太好比较了,因为多了一个维度并且长度是最大体力值。难道说我应该在比较的时候枚举每个可能的体力值来更新这个数组吗?
    GuuJiang
        5
    GuuJiang  
       2021-10-01 12:24:51 +08:00   ❤️ 1
    dp(i, k)表示到达第 i 个镇并且剩余 n 点耐力所需的最小花费
    d[i][j]表示第 i 个镇和第 j 个镇之间的距离
    cost[i]表示第 i 个镇恢复一点耐力所需的价格
    dp(i, k) = min(dp(j, k-c+d[i][j]) + cost[i] * c for j in [0..n] for c in [0..m])
    dp(0, k) = cost[0] * k
    使用记忆化搜索求出 dp(n-1, 0)即可
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2707 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 15:08 · PVG 23:08 · LAX 08:08 · JFK 11:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.