用Python解决编程比赛问题

Question

我遇到了一个问题，觉得解决起来挺有意思的，但就是想不出正确的解决办法。

在一个房间里，有一个怪物，它有 N 颗头，而人类只有 1 颗头。这个人类有两把激光枪。第一把枪 A 发射时可以摧毁 C1 颗头，第二把枪 B 发射时可以摧毁 C2 颗头【这两把枪可以摧毁怪物的头，也可以摧毁人类的头，但优先摧毁怪物的头】。

而且，如果在发射枪后，怪物还有头剩下（也就是头的数量大于零），怪物会长出新的头。使用枪 A 时，怪物会长出 G1 颗头；使用枪 B 时，怪物会长出 G2 颗头。

这个问题是要输入 N、C1、C2、G1 和 G2，然后找出人类必须使用的最短枪选择组合（选择 A 或 B），才能杀死怪物（怪物的头数变为 0 时就死了）。【注意：这个问题来自一个已经结束的编程比赛】

我尝试用递归的方法来解决这个问题，但发现自己对如何真正找到解决方案感到无从下手。所以，如果你能给我一些提示，告诉我该如何着手解决这个问题，那就太好了。

Answer 1

哦，我看到你已经在C++中找到了一个使用Dijkstra算法的解决方案：http://hashsamrat.blogspot.com/2010/10/surviving-monster-programming-problem.html

不过，你似乎在考虑“递归”和其他方法。

解决方案和实现是分开的。所以你真正想做的其实是用同样的算法（Dijkstra算法，简单来说就是一种小心翼翼的广度优先搜索，确保你先走最短的路径），但用Python而不是C++。

你可以逐行复制C++的代码，使用Python的写法让代码更简洁优雅。但你还是在用同样的算法。（另外，你也可以在网上搜索很多人用Python实现Dijkstra算法的方法。或者你可以自己写；你只需要一个优先队列（可以查查维基百科），如果时间不紧的话，你可以用字典和列表的形式写一个性能不太好的优先队列。）

编辑：想想看，如果你所说的“最短选择集”只是指“最少的枪声”，那么其实根本不需要Dijkstra算法；这只是广度优先搜索（当所有边的权重都是1时，广度优先搜索和Dijkstra算法是等价的）。

特别是，生成新节点的逻辑如下：

def howManyHeadsLeft(currentHeads, damage, regen):
    newHeads = heads - damage
    if {this results in blowing off our own head} and newHeads>0: #modify depending on assumptions
        # we killed ourselves without taking monster down with us
        return {} # the empty set of possible search nodes
    else:
        newHeads += regen
        # we could just say return {newHeads} here,
        # but that would be terribly slow to keep on searching the same
        # state over and over again, so we use a cache to avoid doing that
        # this is called dynamic programming
        if {we have never seen newHeads before}:
            return {newHeads}
        else
            return {}

def newSearchNodes(currentHeads):
    return howManyHeadsLeft(currentHeads, atypeDamage, atypeRegen) | howManyHeadsLeft(currentHeads, btypeDamage, btypeRegen)

搜索的“目标”条件是造成足够的伤害来击杀九头蛇，而不伤害到自己（根据假设适当修改）：

heads==1+atypeDamage or heads==1+btypeDamage

当然，也有可能没有解决方案（两种枪的再生能力大于伤害），在这种情况下，这个算法可能会一直运行下去，但可能可以修改为终止。

Answer 2

首先要说的是：Dijkstra算法并不是最优解哦 :)

根据这句话：“枪可以同时摧毁怪物和人类的头。”
我理解是，如果你能射击10个头，而怪物只有5个头，那你是不能杀死它的，因为那样也会杀死你自己，对吗？

无论如何，任何解决方案都应该是这样的形式：
ABABAABBABBB...（一些A和B的组合）

在最后一次攻击时，你会杀死C1或C2个头。在其他每一次攻击中，你会杀死C1 - G1或C2 - G2个头。

如果最后一击是A，你就得用造成(C1-G1)或(C2-G2)伤害的射击来摧毁N-A个头。
如果最后一击是B，你就得用造成(C1-G1)或(C2-G2)伤害的射击来摧毁N-B个头。

任何K都可以用以下形式表示：

X*i + Y*j = K

当然，X和Y必须是互质的，等等。
K个头可以通过i次造成X伤害的射击和j次造成Y伤害的射击来摧毁。

你可以通过扩展的最大公约数算法来找出i和j的值。

求解X = (C1-G1)，Y = (C2-G2)和K = (N-A)
同时求解X = (C1-G1)，Y = (C2-G2)和K = (N-B)
最小的答案就是正确的 :)

就这些啦 :)