导语

上周记录了极客挑战赛的情况,其中一道非常有趣的题,本周继续,本周题目也是游戏,大概的游戏形式是横版闯关类的:
一心的峡谷.png

还是借用网上游戏的图片说明下大概的意思,玩家一个英雄,进入一个场景(横版的),会有一个(每个场景仅一个)怪物与玩家英雄对抗,玩家有血条,有蓝量,6个技能(其中1个技能是升级其他5个技能),然后需要做的就是打到场景中的怪物,冲往下一个关卡。

摸索

有了之前游戏的经验之后,我知道了,上来就是一顿摸索,其实和上周说的游戏类似,客户端是个状态机,英雄有血量和蓝量,每次和怪物对抗之后,客户端会上传一堆指令到服务端,服务端重放这一堆指令,看最终的英雄状态和怪物状态是否合法,是不是英雄还活着,怪物已经死亡,然后就可以进行到下一关。

一共是有9个怪物,一旦进入游戏,可以得到所有怪物的属性:

bosses = [
    {
        "Name": "小壶守卫",
        "Model": "Boss_ball",
        "Hp": 396,
        "Skill1_harm": 63,
        "Skill2_harm": 71,
        "Award_hp": 133,
        "Award_mp": 1695,
        "New_star": 0
    },
    {
        "Name": "苇名二心",
        "Model": "Boss_sword",
        "Hp": 532,
        "Skill1_harm": 59,
        "Skill2_harm": 89,
        "Award_hp": 157,
        "Award_mp": 1678,
        "New_star": 0
    },
    {
        "Name": "古达",
        "Model": "Boss_guda",
        "Hp": 643,
        "Skill1_harm": 57,
        "Skill2_harm": 97,
        "Award_hp": 142,
        "Award_mp": 1362,
        "New_star": 1
    },
    {
        "Name": "中壶守卫",
        "Model": "Boss_ball",
        "Hp": 668,
        "Skill1_harm": 59,
        "Skill2_harm": 67,
        "Award_hp": 178,
        "Award_mp": 1458,
        "New_star": 0
    },
    {
        "Name": "苇名三心",
        "Model": "Boss_sword",
        "Hp": 687,
        "Skill1_harm": 31,
        "Skill2_harm": 101,
        "Award_hp": 212,
        "Award_mp": 2659,
        "New_star": 0
    },
    {
        "Name": "黑古达",
        "Model": "Boss_guda",
        "Hp": 852,
        "Skill1_harm": 77,
        "Skill2_harm": 91,
        "Award_hp": 132,
        "Award_mp": 4157,
        "New_star": 2
    },
    {
        "Name": "大壶守卫",
        "Model": "Boss_ball",
        "Hp": 1502,
        "Skill1_harm": 71,
        "Skill2_harm": 105,
        "Award_hp": 154,
        "Award_mp": 3089,
        "New_star": 0
    },
    {
        "Name": "苇名零心",
        "Model": "Boss_sword",
        "Hp": 1611,
        "Skill1_harm": 97,
        "Skill2_harm": 127,
        "Award_hp": 189,
        "Award_mp": 6493,
        "New_star": 0
    },
    {
        "Name": "超黑古达",
        "Model": "Boss_guda",
        "Hp": 2988,
        "Skill1_harm": 101,
        "Skill2_harm": 153,
        "Award_hp": 0,
        "Award_mp": 0,
        "New_star": 3
    }
]

简单讲一下“Award_hp”和“Award_mp”这两个值,就是你击败怪物后,得到的奖励,可以分别增加对应的hp和mp,其他字段就是对应意思了。

hero = {
    "Hp": 520,
    "Mp": 1806,
    "Power": {
        "Cost_mp": 233,
        "Attack_increase": [
            {
                "skill_i": 1,
                "skill_j": 1,
                "skill_k": 1,
                "skill_l": 1,
                "skill_u": 1
            },
            {
                "skill_i": 6,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 3,
                "skill_u": 4
            },
            {
                "skill_i": 6,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 1,
                "skill_k": 2,
                "skill_l": 4,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 2,
                "skill_l": 4,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 3,
                "skill_u": 5
            },
            {
                "skill_i": 7,
                "skill_j": 2,
                "skill_k": 3,
                "skill_l": 4,
                "skill_u": 5
            }
        ]
    },
    "Skills": {
        "skill_i": {
            "Cost_mp": 489,
            "Attack_hp": 187
        },
        "skill_j": {
            "Cost_mp": 134,
            "Attack_hp": 50
        },
        "skill_k": {
            "Cost_mp": 186,
            "Attack_hp": 70
        },
        "skill_l": {
            "Cost_mp": 251,
            "Attack_hp": 95
        },
        "skill_u": {
            "Cost_mp": 352,
            "Attack_hp": 134
        }
    }
}

经过几次手打的尝试之后,客户端上传的指令,类似["skill", "skill_j"],["attack", "Hero", "Boss", "skill_j"]这两条连续指令,表示英雄发动了技能skill_j,并且命中了怪物,反过来,怪物击中英雄也有类似连续指令,不展示了。手打很容易通过前三关,后面几关越来越难,手残党直接放弃。

思考一番之后,其实客户端只需要传送英雄攻击怪物的动作序列即可,不需要构造英雄“挨打”的序列,嘻嘻~所以问题转换为英雄的蓝量够不够击败怪物。如果不存在技能升级,那么就是一个背包问题,算是一个无限背包问题(实际上整体问题属于一个有限背包问题,因为技能其实是有施放次数上限,这里计算背包问题时,先不考虑)。

确定了是无限背包问题,也有两条建模路径:

  • 确定的蓝量能够产生最大的耗血量;
  • 确定的血量用最少多少蓝量可以完成;

OK,二选一,上来我选择了第一条,很快能写出背包问题代码:

# W指的是最大的蓝量,w是技能耗的蓝量树组,v是技能产生的伤害
# 最后dp返回的数组,每一个元素有两位[x, y],x表示产生的最大伤害,y表示达到这个最大伤害使用的技能序号
def knapsack01D(w, v, W):
    n = len(w)
    dp = []
    for i in range(W+1):
        dp.append([0,-1])

    for i in range(n):
        knapsackComplete(dp, w[i], v[i], i)

def knapsackComplete(dp, w, v, i):
    W = len(dp)
    j = w
    while j < W:
        if dp[j-w][0]+v > dp[j][0]:
            dp[j][2] = i
        dp[j][0] = max(dp[j-w][0]+v, dp[j][0])
        j += 1

虽然背包代码写得很轻松,但是后面就陷入了一个死胡同,我拿着这个函数,疯狂尝试,怎么试呢?前面1~3关我不升级技能,看能不能通过,发现不行,那升一级,发现可以通关,升两级不行,那我就升一级,然后到了4~6关,我再用此策略,结果发现弄来弄去,只能通过4~6关,获得第二颗星星的奖励,死活打不过7~9关怪物。
绝望你经历过吗.jpeg

问题建模

当我要放弃的时候,我看了一眼答案提示,答案没有代码实现哈,但其中有一句话点醒了我:

设状态 dpAi 表示强化i次的情况下,伤害j血量的最小蓝耗,dpBi 表示强化i次的情况下,完成j这个boss之后剩余的最大蓝耗,然后两个dp依次计算,就可以得到最终策略了。

这句话得多读几遍,也就是说,我们可以把所有升级后的对应血量蓝耗情况都计算出来,然后还得多算一个矩阵,表示强化了i次情况下,击败第j个怪物之后,剩余的最大蓝耗,首先上面我算的蓝耗和血量的背包问题,反过来建模,通过确定血量耗最少蓝的结果,去计算击败某个怪物之后剩余蓝量。

想清楚整体模型之后,动手写了代码,确定血量消耗最小蓝耗问题,也不是特别难,基于这个结果,去构建完成j这个boss之后剩余的最大蓝耗,稍微多想下,也可以写出来,代码大致如下:

# 根据hero和boss的数组初始化背包问题相对应的值
# dp最后保存的是血量j对应消耗最小蓝耗
# dp2表示哪个技能实施后达到的最小蓝耗(就是去往下一个最佳状态,需要施放的技能)
v = [489, 134, 186, 251, 352]
w = [187, 50, 70, 95, 134]
ws = [[]] * 11
W = 2988
dp = []
dp2 = []
skills = ["skill_i", "skill_j", "skill_k", "skill_l", "skill_u"]
for i in range(11):
    for j in range(len(skills)):
        w[j] = w[j] + hero['Power']['Attack_increase'][i][skills[j]]
    ws[i] = copy.deepcopy(w)
    t1, t2 = knapsack01D2(ws[i], v, W)
    dp.append(copy.deepcopy(t1))
    dp2.append(copy.deepcopy(t2))

# matrix[i][j]表示i次强化后,怪物j被打败之后,剩余的蓝量
matrix = []
for i in range(11):
    matrix.append([-1]*9)

bosses_hp = [396, 532, 643, 668, 687, 852, 1502, 1611, 2988]
bosses_award = [1695, 1678, 1362, 1458, 2659, 4157, 3089, 6493, 0]
initial = 1806-134

for i in range(11):
    if initial >= (i+1)*233+dp[i][bosses_hp[0]]:
        matrix[i][0] = initial-(i+1)*233-dp[i][bosses_hp[0]]

    if matrix[i][0] >= 0:
        matrix[i][0] += bosses_award[0]

for i in range(9)[1:]:
    if matrix[0][i-1] >= dp[0][bosses_hp[i]]:
        matrix[0][i] = matrix[0][i-1] - dp[0][bosses_hp[i]]

    if matrix[0][i] >= 0:
        matrix[0][i] += bosses_award[i]

print(dp[6][1502])

tracing = [[]]*9
for j in range(9)[1:]:
    r = 0
    for i in range(11)[1:]:
        for k in range(i+1):
            if matrix[k][j-1] >= 233*(i-k) and matrix[k][j-1]-233*(i-k)-dp[i][bosses_hp[j]] >= 0:
                matrix[i][j] = max(matrix[i][j], matrix[k][j-1]-233*(i-k)-dp[i][bosses_hp[j]])

            if matrix[i][j] > r:
                r = matrix[i][j]
                tracing[j] = [k, i]
        if matrix[i][j] >= 0:
            matrix[i][j] += bosses_award[j]

matrix矩阵的最终结果:

[[2096, 2382, 2065, 1779, -1,   -1,   -1,   -1,   -1],
 [1897, 2232, 1967, 1743, 2671, 4680, 3981, -1,   -1],
 [1696, 2067, 1851, 1666, -1,   4508, 3923, -1,   -1],
 [-1,   1866, 1692, 1556, -1,   4331, 3844, 6507, -1],
 [-1,   1679, 1548, 1461, -1,   4160, 3777, 6547, -1],
 [-1,   -1,   1364, -1,   -1,   -1,   3642, 6520, -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3510, 6502, 2],
 [-1,   -1,   -1,   -1,   -1,   -1,   3382, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3236, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   3095, -1,   -1],
 [-1,   -1,   -1,   -1,   -1,   -1,   -1,   -1,   -1]]

可以看到,最终要打败第9个怪物,只有一种升级的可能性,其他升级方法都不可行,但是具体怎么升级呢?眼睛看,也能看出来,就没有写代码找了,因为需要升级的话,肯定是越早越好的,应该在打第一个怪物时做1次升级(本来游戏规定要升级1次,也就是第1行已经是升级过的情况),第5个怪物升级3次,第6个怪物再升级2次,叭叭叭,顺利通关~~
嘬嘬嘬.jpeg

结论

这题的关键是怎么把背包问题建模,并且有连续好几个动态规划的子问题,层层相扣,加上出题人卡的数值,刚刚好只有一个解,我在疯狂尝试我自己方法的时候,也是差不多无助的状态,等到看到提示之后,又充满信心,解决了问题,也算是波谷到波峰的爽感。类似动态规划问题,在极客赛可能算简单的,但是放在平时刷题时,算难度高的,涉及到好几个状态矩阵的计算,又是一个和一个相关联的情况。挺有意思的一题,后面再继续写一篇极客挑战赛~

标签: none

已有 8 条评论

  1. 1 1

    1

  2. 1 1

    555

  3. 不错不错,我喜欢看 https://www.237fa.com/

  4. 看的我热血沸腾啊https://www.237fa.com/

  5. 不错不错,我喜欢看 https://www.ea55.com/

  6. 《比天国陌生》韩国剧高清在线免费观看:https://www.jgz518.com/xingkong/121956.html

  7. 《永恒生活》喜剧片高清在线免费观看:https://www.jgz518.com/xingkong/79930.html

  8. 《史前巨鳄3》剧情片高清在线免费观看:https://www.jgz518.com/xingkong/10453.html

添加新评论