极客挑战赛-笔记二
导语
上周记录了极客挑战赛的情况，其中一道非常有趣的题，本周继续，本周题目也是游戏，大概的游戏形式是横版闯关类的：
还是借用网上游戏的图片说明下大概的意思，玩家一个英雄，进入一个场景（横版的），会有一个（每个场景仅一个）怪物与玩家英雄对抗，玩家有血条，有蓝量，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关怪物。
问题建模
当我要放弃的时候，我看了一眼答案提示，答案没有代码实现哈，但其中有一句话点醒了我：
设状态 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次，叭叭叭，顺利通关～～
结论
这题的关键是怎么把背包问题建模，并且有连续好几个动态规划的子问题，层层相扣，加上出题人卡的数值，刚刚好只有一个解，我在疯狂尝试我自己方法的时候，也是差不多无助的状态，等到看到提示之后，又充满信心，解决了问题，也算是波谷到波峰的爽感。类似动态规划问题，在极客赛可能算简单的，但是放在平时刷题时，算难度高的，涉及到好几个状态矩阵的计算，又是一个和一个相关联的情况。挺有意思的一题，后面再继续写一篇极客挑战赛～
1
555