—— 棘手的问题 ——

无论是对精通铁砧的玩家还是乱敲附魔书的小白，都先试着思考这样一个问题：

一个头盔，一本荆棘 3、一本保护 4 还有一本水下呼吸 3，如何用最少的经验将这 3 本附魔书合并到头盔上？

多数玩家面临这样的问题，可能直接就直接乱敲了，比如直接一本一本敲上去。了解过一些铁砧机制的玩家可能会选择，4 个物品先两两合并，之后再敲一起。那么哪种路线更好呢？

同时，除了合并附魔书的路线，还有顺序问题：当我们把附魔书放上去就会发现，荆棘 3 是比其他两本书都要贵的，整整要 12 级经验。而保护 4 反而最便宜，只要 4 级。所以是先敲贵的，还是便宜的？

—— 巨大的空间 ——

综合来看 3 本附魔书可以产生共 5 种合并路线：

在最左的位置是头盔的情况下，剩下的 3 个位置又各有 6 种放置物品的方法。也就是说，仅仅 3 本书就产生了 30 种不同的结果。

同样 4 本书就会有 14 种路线，24 种摆放，共 336 种结果；7 本书 2162160 种结果；n 本书  种结果。

铁砧基础知识

为了解决问题，我们先来了解一下，铁砧是如何计算单次合并消耗的经验量的。

首先是来自 wiki 的解释：

合并物品的总花费将是下列费用之和：

• 目标物品和牺牲物品的累积惩罚之和。

• 如果同时进行重命名，则额外产生重命名的费用。

• 如果目标物品耐久度未满，则耗费2级用于维修。

• 如果牺牲物品拥有魔咒，则产生附魔费用。

这里我们忽略第二点和第三点，我们只讨论简单的合并情况。

上面涉及到几个概念：

目标物品和牺牲物品：对应铁砧合并时左侧和右侧的物品。（后文直接用左右代替）

累计惩罚：每次铁砧操作后得到的新物品会产生累计惩罚，下次合并消耗额外的经验。

附魔费用：每个附魔都有自己的价值，附魔越贵越多，消耗经验也就越多。

简单来说，消耗经验 = 附魔费用 + 左累计惩罚 + 右累计惩罚

不会用没关系，具体如何计算，我们下面举例说明：

测试三本附魔书：荆棘 3、保护 4 和经验修补。这三本书都是创造直接拿的，所以它们的累计惩罚都为 0。

我们首先来观察组合头盔和荆棘附魔书是什么样的：

这个操作会消耗 12 级经验，同时新物品会多出现一个 tag：RepairCost，也就是上述的累计惩罚。

这里使用的是 Kiwi 模组提供的 NBT 显示功能。除了通过观察 NBT，也可以尝试对物品改名，因为改名固定消耗 1 级经验，所以改名时附魔花费减一就是物品的累计惩罚。

如果我们再尝试其他附魔书可以得到下面的结果：

荆棘 3——12 级、保护 4——4 级、经验修补——2 级

通过这样，我们就得到了附魔书对应的附魔费用，因为次数两个物品的累计惩罚都为 0。

接下来我们尝试合并保护和荆棘，通过上面的表格我们可以算出，这次操作会消耗 12 级经验，当然铁砧也会告诉我们：

之后我们尝试把新的附魔书与头盔合并：

可以看到需要 17 级，这个数字是怎么来的呢。我们知道此时附魔书有 1 级的累计惩罚，所以书的价值就是 16 级，也刚好是荆棘 3 的 12 级加上保护 4 的 4 级。可以得出，附魔费用是线性叠加的。我们也可以认为附魔费用，就是“价值”，新书的价值就是两个书的和。

那么累计惩罚如何计算呢，对于新物品（新获得的、新合成的、没有经过铁砧操作或被砂轮抹去附魔的物品），它们的累计惩罚都为 0。经过一次铁砧后变为 1，之后 3、7、15 …… 。或者说每次都是前一次的两倍加 1 也就是 2n+1。当然这里的前一次指的是左右两个物品中惩罚较大的那个。

现在我们知道了计算一套合成的全部方法：

• 通过改名可以知道一个物品的累计惩罚；右边放书可以获得附魔费用。

• 合并后价值（附魔费用）是两个物品价值相加；累计惩罚变成两倍再加一。

铁砧计算方法

现在我们可以脱离铁砧进行模拟计算了，这里我们用一个 wiki 上的例子实践一下：

这是一个一共消耗 68 级经验的靴子附魔合成。

因为我们不关心是对靴子还是对什么别的物品合并，也不关心附魔书是什么，我们只关心所有物品的价值和惩罚，所以让我们把这个过程抽象为一颗二叉树：

其中，每一个节点代表一个物品，数字代表物品的价值；每条边代表物品合并需要额外花费的惩罚。这样改成树更有助于我们计算。此时我们只要把所有的右侧节点（紫色）数字相加，再把所有边上的数字相加，就得到了总的经验花费。对于这个例子则是 58 + 10 = 68。

至此，我们学会了如何口算模拟计算铁砧消耗。

既然教会了大家如何计算铁砧消耗，那么这篇专栏就到这里了……？

探索最小经验之路

什么，你问怎么解决之前说的经验最小化问题？啊这，你真的这么想听吗，那我们借助二叉树再把问题抽象化。

请解下面的算法题：

题目：

给定 n 组数字，分别代表 n 个节点（物品）的价值和惩罚。用这 n 个节点作为叶子节点构建一颗二叉树：父节点的价值是叶子节点的和，惩罚是叶子节点中较大的那个乘 2 并加 1；节点的惩罚标注在其与父节点链接的边上。全部节点计算完毕后，树的最终得分为：全部右节点的价值和加边上的惩罚和。

要求：

根据给定的输入，构建出满足要求的得分最小的二叉树。

可是我也不会，所以你来帮我算吧！我溜了！

开玩笑的，我还是会在这里进行解题的，然而没开玩笑的是，我确实不会解上面这道题。但是我可以帮你解开这道题的变种：去除输入惩罚后的题目。如果没有输入惩罚，只有价值的情况下，这道题其实简单一些。

在正式解题之前，可能不少观众会觉得：哇…这，这我也算不过来啊，有没有个简单结论直接告诉我怎么搞。

或者说只是单纯的太长不想看，那么这里就是一个简单结论：别多想，两两合并，就像上面 wiki 那个例子一样。

如果你还要更好一点，那么：在两两合并的基础上，装备第一次敲附魔书的时候，和最贵的那个合并。剩下的就…随缘吧。

我们来分析这道题，把这道题分成几个步骤：

1. 构建一颗 n 个叶子节点的二叉树

2. 将价值排序填入树中

3. 计算树的分数

不断重复这些步骤，直到比较出分数最小的树。

那么我们先挑最简单的来：计算树的分数 将价值填入给定的树中

我们依然使用上面的 wiki 例子：

因为我们限定所有输入物品惩罚都是 0，所以在树结构固定的情况下，总惩罚也是固定的（对于这个例子也就是 10）。因此我们要做的就是如何填入价值，让所有紫节点的和最小。

对于价值和，我们先试着填入未知量：

于是我们可以得到这棵树的价值和是：a+c+e+g+(b+c)+(f+g)+(d+e+f+g) = a+b+2c+d+2e+2f+3g

我们可以这样理解，未知数的系数就是它出现在右节点的次数，通过从上到下标注每个节点出现在右侧的次数，就可以快速得出紫色节点的和。

这样我们可以快速得到叶子节点的系数：1 1 2 1 2 2 3

我们可以尝试带入例子中的的价值：

可以看到计算与实际结果一致，也就是说我们可以计算每个叶子节点的系数作为权重来快速计算价值和。

而且通过计算可以发现，同系数时价值互换对结果不会产生影响。所以为了价值和最小，有如下算法（也是后面会用到的书本排序算法）：

1. 计算全部叶节点权重

2. 按照节点权重升序填入降序的价值

至此，我们得到了比较两棵树好坏的方法：

• 权重和惩罚相同，两棵树等价

• 权重相同的情况下，惩罚和小的树好

• 惩罚相同的情况下，权重较低的树好

• 都不同的情况下，需要带入书本价值计算

接下来我们解决另一个问题：如何确定树的结构

然而到现在为止，我们一直在简化模型，但需要计算的树的数量一直没有改变。如果还是 n 本书有  种树的话计算量依旧很大。 

但是与其从零开始构建一棵树，不如在之前的基础上更新。所以，我们可以尝试先构建 1 本书时候的树，然后向这棵树添加新的节点。每次使用贪心算法的思想尝试做到最好。这样逐渐得到 2 本书时候最优的树，直到 n 本书。至少这样不用把所有的树都暴力搜索一次，而是一次性得出最好的树。

虽然贪心的结果不一定是对的，但至少我们先试试。

那么先来看最简单的一棵树：

对于这棵树接下来有两个生长方向：

可以看出来，两棵树的惩罚和是相同的，但是左树的权重更低，就意味着消耗的经验更少。

所以我们可以得出结论：向左生长优于向右生长。

我们接着左树继续生长，依然有两种结果：（现在起紫色标注改为叶子节点）

现在出现了分歧：左树惩罚低但权重高，右树惩罚高但权重低。

这里我们可以这样理解：选择左树就是选择多算一次附魔书的价值（因为权重是系数），选择右树就是选择 +2 经验惩罚。

这样事情就清楚了，如果书比较贵，那就选择右侧，如果书便宜那就选择左侧。

所以让树生长，无非只有两种选择：向右生长和向左下生长；具体的生长方向取决于书的价值。

然而这并没有太大帮助，无非只是排除了右下生长这一种情况。

我们还有很多问题要解决：

• 权衡生长方向时选择什么书的价值作为标准，最贵的还是最便宜的？

• 继续生长下去单次生长的可选位置增多，可能会产生不同的分支，如何确保结果不是局部最优解而是全局最优解？

• 这样贪心算法的结果一定是对的吗？

这些问题暂时还不能解决，但是现在的模型还有优化的空间。

通过观察二叉树，我们可以搞点骚操作：因为每次铁砧操作必定是两两合并，所以最后叶子节点一定是成对的，每次生长都会增加两个节点。如果我们去除所有的叶子节点转而观察所有的“合并”操作，是不是可以简化模型？

比如这样一颗 5 层的树：

这样做有什么好处呢？通过简化掉叶子节点，可以减少层数；同时因为节点的性质从物品变为了合并操作，所以生长时只需要添加一个节点即可。

接下来我们需要验证新模型是否可以继承之前的性质：

• 对于惩罚：显而易见因为删除的叶子节点的惩罚均为 0，所以惩罚不会产生任何变化。

• 对于权重：因为权重是自上而下计算的，所以我们可以通过加回叶子节点的方式补回到原来的树来计算。所以新模型叶子节点权重小，那旧模型也一样小。在接下来的计算中也可以得到体现。

接下来我们对先前的结论做一些思考：“向左生长优于向右生长”，这是我们之前得出的对单个节点而言的结论，那这个结论是否可以拓展到全局呢，思考向这样一棵树添加节点：（这里为了理解，用正方形显示被删去的叶子节点）

可以看到对于这 4 个可以生长的方向（虚线圆所示）中，所有情况都会让树的层数增加，而且所增加的惩罚是等同的，所以我们只需要比较他们增加的权重，就可以判断哪里是最优的生长方向。

对于4个方向中有两个右节点，根据之前的左优于右生长规则，这两处都是不好的生长方向。那么还剩下两个左节点。

此时我们比较他们产生的新权重：如果选择左 1，权重的变化是 0 -> 0, 1； 如果选择左 2，权重的变化是 1 -> 1, 2。左 2 的权重是比较高的，因此最优的生长方向是左 1。所以左右优先原则在简化后的模型上依然适用。

事实上对于任意一个方向的生长，其权重的变化均为 x -> x, x+1，也就是说 x 高的其权重也高（即可以不去看方块节点的权重，而直接去看圆节点）。

权重是方向决定的，每向右一次，权重就增加 1，这意味着在选择生长方向时，左侧总是优先于右侧，也就是说对于单个节点的左右优先规则对于整棵树也适用。进而我们还可以推论出，整棵树延伸最远的地方，一定是最左侧。

基于这个结论，我们可以对需要生成的树按照层数进行分类。比如我们要生成一颗 10 个节点的树（10 次合并操作或 10 本附魔书加 1 个物品）可以生成一颗高度（深度）为 4 的最优树，然后是高度为 5、6、7 …… 10 的最优树。之后将这些树进行比较再得出一个最优解。

这样做的好处是固定了树的高度，防止树乱生长，同时也减少了计算量。因为在除了最左侧的位置再往深生长不是最优的。现在我们才真正有一个构建树的起点。

现在我们开始尝试构建一颗树，这里以高度为 4 的树为例。

首先构建主要路径（做左侧分支）

如图最左侧为主要路径，虚线为接下来可生长的位置。

可以观察到，可以生长的三个位置，同惩罚也同权重，所以均为等价位置。那么看似会产生三条分支，这里选择最上面的作为生长方向演示。

接下来我们有 4 个可生长的位置，其中相同颜色的为等价节点。这里其实我们可以看出一个新结论：一个节点产生的新位置一定比本身要差。不难理解，作为一个新节点，肯定是没有后代节点的，所以无论是向左还是向右生长，都会产生额外的惩罚，更不用提向右还会增强权重。

利用新的结论，我们可以知道，蓝色优于黄色和红色。因为黄色和红色的父节点和其他蓝色是等价的。

所以如果继续生长也是在蓝色位置选择其一，同样再产生的新节点，还是没有剩下的那个蓝色节点好。因此选择两个节点之后，两个蓝色节点都会使用。正因为等价节点会被如此接连使用，可以得出：等价节点不会产生分支。那么之前说的产生分支也就不存在了。

让我们继续。

按照左右优先原则，先选择蓝色。

到这里，我们才遇到了第一个分支情况。首先我们可以排除红色。接下来蓝色和黄色选择哪一个？

蓝色会增加 7 点惩罚和 1 权重，黄色会增加 1惩罚和 2 权重。也就是说，是选择多 6 点惩罚还是多一本书的价值。如果多一本书，哪一本书？（这也对应了之前的问题其一）

这里提前说结论，用来参照的书，是所有书中价值最小的那本。我会在后面提供解释，但现在先让我们继续。

如果书价值大于 6 那么选择蓝色：

此时接下来三种情况等价。并且最终会顺利填完全部位置。

如果书价值小于6 那么选择黄色：

因为之前存在等价节点，所以这里我们面临相同的选择，但是这一次我们不能用最便宜的书了，因为我们已经使用过了，所以我们要用第二便宜的书作为判断标准。

如果第二本书依然便宜：

否则：

虽然这里产生了分支，但是请注意如果再增长一个节点，两个分支又会合并：

可以看出，当等价态出现时，不管如何选择，再增长的状态下都会最终合并。又因为我们保持每一个分支都是最优的，所以就算是在分支合并前停下，得到的结果也是属于这一高度的树的全局最优解（对第二问题的回答）。同时正因为会合并，所以贪心算法是可用的（第三个问题）。

接下来无论怎样也都可以顺利填完 4 层，也就是 15 个节点。如果我们不需要这么多节点，只需要在节点数达到目标时停下即可。

现在让我们解答遗留下来的第一个问题：为什么选择价值最小的书？

根据之前的书本排序算法，我们知道权重越大的节点，最后分配到的书价值也就越小。所以这个问题可以转换成，此时节点权重一定是最大的吗？（这里指的节点是面临选择时权重较大的那个节点，因为面临选择时都是一个节点权重大惩罚小，另一个权重小惩罚大，因为惩罚是可计算的，所以需要书才能判断的节点是两者中权重大的那个。）

对于这个问题，我们可以假设存在一个更大权重的节点：

在这里面临选择的是黄色和蓝色节点，此时存在一个权重更高的红色节点，意味着黄色不能被分配到最便宜的书。

从这里我们开始分析，既然红色节点存在，而且自己的权重大于 0，那么它自己一定在某棵子树的右节点上。换句话说，红色节点的祖宗节点，一定有一个是右节点：

同时，既然这个祖宗节点存在，而且是作为右节点，根据之前的左右优先原则，有右节点的前提一定是左节点存在。于是也肯定存在绿色这样一个等于黄色节点权重的节点。

既然绿色已经存在，那就说明绿色比黄色更优，或者等价。但是黄色作为可选的新生节点，就算存在，其惩罚也一定为 1。所以绿色的惩罚一定小于等于 1。显然作为合并节点，惩罚不可能小于 1。所以绿色必然和黄色等价。现在，根据等价节点优先的规则，此时惩罚和权重都更差的红色节点就必然不能存在。因此当冲突存在时，不可能存在权重更大的节点。甚至可以说，在任何时候，都不可能存在一个权重高于所有可选节点的权重的节点。

现在我们解决了之前遗留的全部问题，也得出了一个合理的树构建算法。

接下来，对于其他层数的树也做像上面一样的构建操作，直到节点数达到目标。

最后针对每一棵树排序出最优书本顺序（书本排序算法），并计算出分数。这样我们就可以比较出所有树中最优的那一个。

代码实现

下面是一份铁砧最小经验算法的 Python 代码实现

现在我们唯一需要解决的问题就是，如果最开始附魔书有惩罚怎么办？

我不会 ¯\_(ツ)_/¯ ……

未完待续？