老婆大人喜欢刷阴阳师。最近也是被她带着一起入坑了，每天在同一个寮里刷结伴同行刷得不亦乐乎。

　　阴阳师里面每天有两回悬赏封印任务，早上一次，晚上一次。任务里要打各种妖怪，完成任务的话就会有级别不等的奖励。阴阳师里的妖怪有上百种，关卡则有数百种。除了非常常见的妖怪，比如几乎每次都会出现的鲤鱼精或跳跳犬，哪里会记得所有妖怪所在的关卡呢？

　　这么一来，每次打悬赏任务，不免都要去搜索「阴阳师 XX 哪里多？」。可是，即使搜索到了结果，也未免就是最优的。比如，「甲关」里可能有 3 个妖怪 A，2 个妖怪 B，「乙关」里则有 3 个妖怪 B 和 1 个妖怪 C。如果我正好遇到了同时要打妖怪 A 和 B 的任务，那打「甲关」就更划算；如果遇到了只要打妖怪 B 的任务，那打「乙关」就更划算。

　　在阴阳师里，攻打一个关卡需要体力值。体力值每 5 分钟回复 1 点，上限只有 100 点。虽然也能购买体力，并且有其他获取体力的方式，但总的来讲，体力是有限的，是最没法氪金的东西。不管你是萌新还是大佬，每天都只有这么多，体力用完了就只能等恢复了。

　　那么，每天的悬赏封印，包含这么多关卡和怪物，到底怎样选择关卡组合，才能够最节省体力值，方便老婆大人去打其他任务呢？

　　花了几天时间，写了一个任务规划器。输入悬赏封印需要完成的怪物名、数量和星级，给出一个推荐的规划方案。并且包含了几个可选项：是否攻打御魂副本（及限定层数），是否攻打秘闻副本（及层数）。探索副本是默认攻打的，是否攻打首领则作为单独选项，不勾选的话会限定不去打首领。是否组队选项会影响御魂副本的消耗体力，不组队是 6，组队是 4。同时，组队的话，就可以去打妖气封印。

　　打完这么多任务，一共需要 39 点体力。如果你体力正好吃紧的话，也可以往下拉，放弃 1 星任务，只打 3 星及以上任务。这个程序会按星级从低到高分别给出策略。最右边放了一个简单的计数器，去对应关卡刷怪的时候方便计数，免得忘记打了几次。

　　刚才选项中还选择了攻打秘闻副本。秘闻副本每一层都有 3 个回合，经常出现高等级的怪。但是秘闻副本层数高了之后非常难打，所以通常我会设限定只打 1-3 层。如果我们不打秘闻副本，只打探索副本的话，策略就变成了：

　　体力消耗变成了 75，几乎翻了一倍！（这次是因为跳跳妹妹在探索副本中只有 15 章的首领中才有）

　　这个程序，原以为两三天就能搞完的，实际花了差不多一个礼拜。阴阳师的关卡和怪物众多，光洗数据就花了很久。另外，首领副本的计算需要特殊对待，试了几个方案之后才实现。

　　程序仍旧是用我熟悉的 Python PyQt5 写的界面，用了 pulp 包和 numpy 计算方案。完整代码已经上传到luyaozou/yys_mf_optimizer。——这又是一个所依赖的包（上百 MB）比自身（~1 MB）大得多的程序。毕竟我也就只有能力写点这种小东西了。

　　这个程序背后是如何工作的呢？下面就会讨论具体数学模型，比较技术，可以不看。

　　毫无疑问，悬赏封印任务的策略选择，肯定是一个「优化」问题。打了一番草稿之后，我把模型搞清楚了。

　　这是啥？这是一个典型的整数线性规划（integer linear programming）问题嘛！不过，搜一下维基，发现整数线性规划问题竟然是 NP-hard 问题。好吧，就不作死挑战自己写算法了，开始搜轮子。

　　解线性优化的 python 包有好几个。简单看了文档之后，选了一个比较简洁明了的包：pulp。这个包设定待解问题的方式直白，几乎就是原样输入数学公式。例子如下：

　　可以说是直接把问题对应的数学方程一个个加到 prob 对象里面就可以了。当然更复杂的向量和矩阵输入可以用嵌套循环，或者调用 numpy。

　　一个是，它只会给出一个最优解，而不是所有最优解。如果你想要遍历所有可能的最优解，就需要设一个循环，每解出一个最优解，就把自变量不能再等于这个最优解的条件添加到 prob 对象里面，然后再次求解，直到返回无解为止。因为整数线性规划是 NP-hard，遍历所有可能解这种操作，小心算爆掉哦。不过，阴阳师这个问题中，我们并不需要遍历所有解，只要告诉老婆大人一个可行解就可以了。

　　第二个坑，是它返回的结果 prob.variables()，里面的元素顺序和你初始定义的自变量列表 [x] 不一样，是乱的。这应该和 pulp 内部采用的算法有关。所以，你只能使用

　　这样的语句。第二种语句中的索引号 i 会和初始的其他列表不一致。我在这里被坑了一次。

　　对阴阳师悬赏封印的问题来说，还有一个比较难搞的地方就是首领关卡。首领关卡是阴阳师中的一个设定。在探索副本里，每一个章节都有 5-7 个小怪和一个首领。首领只有在连续打了若干个小怪后才会出现，但这个数目是随机的。有的时候，打 3 个小怪就能出首领，有的时候则要把章节内所有小怪全打完才能出首领。这样一来，如果在优化过程中，选择攻打首领关卡的话，它的体力消耗值就不是定值。

　　在这个程序里，我没办法模拟首领出现的随机情况，只能假设最坏的情况：所有小怪打完后首领才会出现。这就为优化增加了一层复杂性：如果一个章节中的小怪关卡都没有悬赏封印任务要求的怪物，只有首领关卡有的话，攻打首领显然不划算。可如果其他小怪关卡也有一部分符合任务要求呢？到底是选择连同小怪和首领一起打，还是到其他章节另觅只需要打小怪的策略呢？

　　查询解中是否存在首领关卡。如果存在，从数据库中把与其相关联的同章节其他小怪关卡

　　来说，它们也是符合任务要求的，本来就可以单独攻打。但同时为了打出首领，攻打

　　的次数要 = 攻打首领的次数。这是新的 constraint，需要加到 prob 里面。对于

　　，它们里面没有任务需要打的怪，所以纯粹是为了把首领打出来才去打的，所以有多少个

　　米乐 M6

　　的限定条件和首领关卡的体力之后，重新求解问题 prob，得到一组新的解。

　　米乐 M6

　　举个例子：食梦貘在探索副本中是比较稀少的怪，只有第 14 章的「涂壁3」里有 1 个，首领里有 5 个。但打首领的线 个体力。所以，如果要打 6 个食梦貘，保险起见就直接打 6 次「涂壁3」就好了。不过，第 14 章中其他的怪还有很多，比如有很多天邪鬼赤。如果同时需要打食梦貘和天邪鬼赤，数量足够多的情况下，就是打首领更划算了。