这是一个创建于 1350 天前的主题，其中的信息可能已经有所发展或是发生改变。
已知玩家有金币和木头两种重要资源，当前金币 0，木头 0，不过金币现在已经每秒自动增长 512 。
玩家在拥有 18000 金币 时可以选择购买一个精灵，精灵每秒钟能采集 10 个木头。
玩家在拥有 800 木头时可以选择开发一个矿脉，矿脉每秒钟能生产 32 个金币。
现在玩家需要在最短的时间内拥有 10240 个木头，那么如何出装最好？
====
想问下这个算法题有什么思路解 谢谢
玩家在拥有 18000 金币 时可以选择购买一个精灵，精灵每秒钟能采集 10 个木头。
玩家在拥有 800 木头时可以选择开发一个矿脉，矿脉每秒钟能生产 32 个金币。
现在玩家需要在最短的时间内拥有 10240 个木头，那么如何出装最好？
====
想问下这个算法题有什么思路解 谢谢
 |
1
Raven316 2021-03-24 20:46:27 +08:00
让我想起点点点生产 cookie 的那个游戏
|
 |
2
66450146 2021-03-24 20:55:45 +08:00
BFS 暴搜应该就可以了，每次都从下一个能操作的时间点开始
|
 |
3
yeqizhang 2021-03-24 20:57:34 +08:00 via Android
QQ 三国吧哈哈哈
|
 |
4
zhongrs232 2021-03-24 21:01:03 +08:00 via Android  1
巨魔与精灵，老游戏了
|
 |
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 欢迎捉虫 |
 |
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 |
Select Language