V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Newyorkcity
V2EX  ›  问与答

请教一个算法题,来自自己玩游戏时的疑惑。

  •  
  •   Newyorkcity · 2021-03-24 20:42:09 +08:00 · 1321 次点击
    这是一个创建于 1324 天前的主题,其中的信息可能已经有所发展或是发生改变。
    已知玩家有金币和木头两种重要资源,当前金币 0,木头 0,不过金币现在已经每秒自动增长 512 。

    玩家在拥有 18000 金币 时可以选择购买一个精灵,精灵每秒钟能采集 10 个木头。

    玩家在拥有 800 木头时可以选择开发一个矿脉,矿脉每秒钟能生产 32 个金币。

    现在玩家需要在最短的时间内拥有 10240 个木头,那么如何出装最好?

    ====

    想问下这个算法题有什么思路解 谢谢
    6 条回复    2021-03-25 07:04:22 +08:00
    Raven316
        1
    Raven316  
       2021-03-24 20:46:27 +08:00
    让我想起点点点生产 cookie 的那个游戏
    66450146
        2
    66450146  
       2021-03-24 20:55:45 +08:00
    BFS 暴搜应该就可以了,每次都从下一个能操作的时间点开始
    yeqizhang
        3
    yeqizhang  
       2021-03-24 20:57:34 +08:00 via Android
    QQ 三国吧哈哈哈
    zhongrs232
        4
    zhongrs232  
       2021-03-24 21:01:03 +08:00 via Android   ❤️ 1
    巨魔与精灵,老游戏了
    BiteTheDust
        5
    BiteTheDust  
       2021-03-24 22:44:53 +08:00   ❤️ 1
    首先显然有钱就应该一直买精灵,因为钱只能买精灵而且不能出产目标物品也就是木头。
    所以在我们的决策就只有是否应该建造更多的矿脉。
    假设我们决定建造 x 个矿脉,那么显然在我们建造出 x 个矿脉之前,应该一直够资源就建造。
    确定 x 的值之后,所需时间就是固定的了。
    又显然精灵不会建造多于 1024 个,所以我们可以直接迭代模拟这个建造过程,枚举 x 即可。
    ————————
    然后按这个思路跑了下程序似乎建造 0 个矿脉是最快的,需要 287 秒。
    https://paste.ubuntu.com/p/5qdFwx7T37/
    代码中的数字已经除过 lcm
    欢迎捉虫
    msg7086
        6
    msg7086  
       2021-03-25 07:04:22 +08:00   ❤️ 2
    1. 如果要造矿脉,越早造越好。
    2. 造矿脉会拖累游戏进度。

    所以写个函数,有钱就造矿脉,造到上限,然后对比一下总的时间就行了。

    10240 的话,造出来不划算。
    Reaching target at time 385s, gold 17120, lumber 19110, seirei 10, mines 0
    Reaching target at time 386s, gold 8976, lumber 19200, seirei 11, mines 1
    19110 个内,造矿脉都是不划算的。

    从目标 19120 起,造 1 个矿脉追上不造矿脉的时间,21190 起,造 1 个矿脉比不造要快。
    23960 起,造 2 个矿脉更快,26440 起 3 个,28970 起 4 个,33170 起 5 个,35560 起 6 个,37900 起 7 个,40200 起 8 个……

    代码在 gist:
    https://gist.github.com/msg7086/9b9f517209c655045c2ecc21994ac0ea
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3584 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 04:18 · PVG 12:18 · LAX 20:18 · JFK 23:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.