前言
阴阳师妖怪屋小游戏作为阴阳师系列的第四部作品在前几天正式发布上线了，作为阴阳师老玩家的我，自然也要凑一个热闹。游戏的整体玩法是抽卡、弹球和养成，我们今天要说的，就是关于获取食材喂养式神的主要途径——探索。
规则
探索玩法的规则是这样子的：我们需要派出我们的小式神组建一个小队，其中部分式神之间具有羁绊，不同的羁绊会有不同的加成比例。探索队伍的坑位和通过的关卡数有关，小队内最多有8个式神。所有式神之间的羁绊规则如下表：
| 羁绊名 | 相关式神 | 加成 |
|---|---|---|
| 春天在哪里 | 樱花妖, 桃花妖 | 2% |
| 干了这杯酒 | 酒吞童子, 茨木童子 | 4% |
| 锅蛙赛跑 | 山兔, 孟婆 | 2% |
| 黑白无常 | 鬼使黑, 鬼使白 | 2% |
| 欢喜叠叠乐 | 镰鼬, 铁鼠 | 2% |
| 来自崇天高云 | 少羽大天狗, 大天狗 | 4% |
| 老板您说 | 鬼使黑, 鬼使白, 阎魔 | 3% |
| 女孩当自强 | 白狼, 妖刀姬, 萤草 | 4% |
| 女子修炼组合 | 白狼, 妖刀姬 | 3% |
| 三途川一日游 | 傀儡师, 阎魔 | 3% |
| 诵经爱好者 | 独眼小僧, 蝴蝶精 | 2% |
| 天邪鬼四 | 天邪鬼赤, 天邪鬼青, 天邪鬼黄, 天邪鬼绿 | 2% |
| 为了大义 | 大天狗, 雪女 | 3% |
| 我的偶像 | 萤草, 白狼 | 2% |
| 养狗还是养猫 | 九命猫, 犬神 | 2% |
| 捉蝴蝶的妖 | 蝴蝶精, 巫蛊师 | 2% |
比如说，我在8个坑位中派出下面这个队伍：
在这个队伍中，因为我派出的式神凑齐了上边表格中的“女子修炼组合(3%)”、“我的偶像(2%)”，“黑白无常(2%)”，“女孩当自强(4%)”，“老板您说(3%)”以及“三途川一日游(3%)”，加起来也就是凑够了17%的加成：
当然，羁绊的加成越高，那也就意味着我们的收益越高。手算怎么获取最大加成，对我这种没抽齐卡池的，算起来还是比较花时间的。那么，我们可不可以自动的去根据我们已有的式神，计算探索队伍的最优项呢？
分析
到此为止，游戏规则我们已经清楚了。试着把表述的再简洁一些的话，那就是：对于式神集合$ \Omega = { \omega_0, \omega_1, … }$来说，在羁绊规则函数：$ f(\omega^i), (\omega \in \Omega , 2 \le i \le 4)$的约束下，选取$k, (k \le 8)$个式神，尽可能的让所选式神构成的$ f(\omega^i) $之和最大。
观察刚才的问题描述，我们需要在8个坑位挑选不超过8个式神，使得总加成最大。很直接的，我们可以想到0-1背包问题。在这里我们回顾一下0-1背包问题：
假如我们有$n$种物品，每种物品只有1个，其中物品$j$的重量为$w_j$，价值为$v_j$，背包最多能承受的重量为$W$，我们希望在背包内尽可能装下总价值更高的物品。
看看，是不是差不多对应上了：$n$个物品对应$n$个式神，每一个式神$j$的“重量”$w_j$都是1，“价值”，也就是羁绊加成，由羁绊规则来确定；在探索队伍这个容量为$W$背包下，希望让价值最大化。这其中，唯一没有对应上的就是“物品”的“价值”，根据羁绊规则，当两个或者多个式神凑在一起的时候，“物品”才有了价值，单独的一个式神是没有任何加成的。因此，我们需要对羁绊规则进行进一步分析。
根据羁绊规则表，我们最终的选择显然是满足以下条件的：
- 当前没有的式神，一定不是最终队伍中选择的式神；
- 最终队伍中选择的式神，一定是羁绊列表中列出的式神。
两句话看似废话，其实可以告诉我们很多信息：首先，由于我们的式神并没有覆盖全卡池，因此假如说我没有茨木童子，那么对于“干了这杯酒”这个羁绊来说，我肯定是凑不齐的了。因此，我们根据已有卡池，在羁绊规则中过滤掉与我们没有抽到的式神相关的羁绊，从而删除了无效羁绊。
第二：我们在选择候选式神的时候，只需要从羁绊列表中选取部分羁绊规则，使得这些羁绊的加成最大，并且羁绊中涉及到的式神数不超过最大坑位数。
那么，如果从羁绊规则的角度考虑的话，我们可以把每一个羁绊规则看作一个“物品”，它的“重量”指的是规则中涉及的式神数量，“价值”指的是这个羁绊对应的加成。这样一来，就完美的对上了0-1背包问题。
但是，这其中还有一个小问题：把每一个羁绊规则看作一个“物品”时，不同的“物品”之间可能有重叠。举个例子：“女孩当自强”这个羁绊中涉及到了白狼、妖刀姬和萤草，但是对于“我的偶像”这个羁绊，它也涉及到了白狼和萤草。而这两个羁绊中涉及到的白狼和萤草其实是同样的式神。换言之，物品的重量可能会相互影响。
为了解决这个问题，其实我们只需要在每次选择一个规则的时候，重置一下其他规则的“重量”： 比如说当我们选中“女孩当自强”这个羁绊规则的时候，也就意味着我们选中了白狼、妖刀姬和萤草。那么，选中它之后，我们临时将白狼、萤草、妖刀姬的“重量”都置为0，于是，在探索队伍中选中“女孩当自强”这个羁绊的情况下，“我的偶像”这个羁绊的“重量”就变成了0。对于背包问题来说，我们优化的目标是尽可能的在包里塞下贵的东西，一个重量为0但是又有价值的东西来说，为什么不把它装在包里呢？
综合以上，我们得出了我们的递归公式：
$g(k, rules) = max(g(k-rule.weight, handler(rules, rule)))$，
其中：$rule$表示羁绊规则中的任意一条羁绊，$handler()$表示一个函数，它将根据选中的羁绊，重置全部羁绊规则。
演示
根据上边的分析，下一步当然就是实现啦。主要就是根据上述分析，实现了个递归，然后写了个网页。效果图大概是这样的：
代码
页面的体验地址点击这里(http://tools.maotoumao.xyz/ygw-jiban/)；
代码就不贴了，github地址点击这里；gitee地址点击这里，有兴趣的自己看叭。
