合成步骤优化

STEPS 显示模式背后 Calculation.getSteps(List<LabelT> startingInventory) 的两段式实现： 先尝试贪心重排，失败则退回朴素的逆序合并。

基本信息

属性 值
实现位置 AbstractCostListService 匿名 Calculation 的 getSteps(List<LabelT>)
输入 getInputs()（原始材料）+ 玩家背包 getInventory()
策略 贪心（带「优先合并相同配方」启发式）+ 回退
复杂度 标签数受控时接近平方；理论最坏三次方
无回溯 一旦走进死胡同不回溯，直接放弃贪心

源码里对这个权衡有明确注释（原文大意）：

没有回溯，所以可能会卡在角落；一旦卡住就退到下面那个更简单的解法。 只要模拟背包里的标签数量保持有界，这个算法接近平方复杂度（和回退法一样）。 理论上如果有很多种不同标签的大量富余产出，可能会退化到三次方，但实践中不成问题。

第一段：贪心重排

模拟背包的建立

startingInventory = 玩家背包标签 + getInputs()
inventory = costLists.newCostList(startingInventory)
remainingProcedureSteps = procedure 的副本
optimizedSteps = []

模拟背包从「已有物品 + 全部原料」开始，之后逐步被消耗掉。

每轮选步规则

对 remainingProcedureSteps 从后往前（i = size-1 → 0）扫描，对每个候选：

candidateInventory = mergeCostLists(inventory, recipeAsCostList(step.recipe, step.multiplier), false)
if (!isAllPositive(candidateInventory)):  continue      // ← 拒绝不可能的计划
inventorySize = estimatedNumSlotsTakenBy(candidateInventory)

isAllPositive 要求每一项 getLabelAmount(label) >= 0，否则该步被跳过：

for (ILabel label : getLabels(candidateInventory)) {
    if (getLabelAmount(label) < 0) return false;
}
return true;

源码注释：Don't give the user an impossible plan.

三条选择规则（按优先级）

优先级 条件 动作
1 第一个 isAllPositive 通过的候选 直接选定它，并 continue（不再比较后面的）
2 step.recipe.equals(preferredRecipe) 而当前最优步不是 立即选定并 break
3 inventorySize < sizeOfInventoryAfterBestStep 替换为槽位占用更少的候选

preferredRecipe = 上一轮已选步骤的配方（optimizedSteps 为空时是 null）。

规则 1 的 continue 是排序扫描 + 首次命中即锁定：因为循环是从后往前扫， 「第一个」实际上是 procedure 末尾最早的候选。规则 2 一旦触发就 break， 因为后面（更靠前）的候选不可能更好。

合并相同配方

选定步骤后：

if (!optimizedSteps.isEmpty() && bestStep.recipe.equals(preferredRecipe)):
    latest = optimizedSteps 最后一项
    latest.two = latest.two + bestStep.multiplier     // ← 倍数累加，合并成一步
else:
    optimizedSteps.add(new Pair<>(recipe, multiplier))

所以连续使用同一配方的多个 procedure 步骤会被折叠成一条，其倍数是两者之和。

死胡同处理

若一轮下来 indexOfBestStep == null（所有候选都 isAllPositive 失败）：

optimizedSteps = null
break

optimizedSteps == null 表示贪心失败，控制流落入第二段回退逻辑。

remove(indexOfBestStep) 用的是 int 强制转换（remove((int) indexOfBestStep)）。 源码注释说明为何不用 LinkedList：Java 的 LinkedList 本来就要重新遍历； 而 ArrayList 的 Array.copy 很快，且刚刚才做过一次线性扫描，不会恶化复杂度。

贪心成功时的返回值

对每个 Pair<Recipe, Long>：

outL = 配方产物标签（过滤 EMPTY）
outC = newNegatedCostList(outL); multiply(outC, -pair.two)
retLabels.add( costLists.getLabels(outC).get(0) )      // ← 只取第 0 个，即主产物

每一步只输出一个标签——主产物。 multipliedRecipeOutputs 的注释说明了原因： recipe.outputs * multiplier; 1st item is the main output。

第二段：回退方案

贪心失败时执行：

ret = procedure.map(step → getLabels(step.multipliedRecipeOutputs).get(0))
Collections.reverse(ret)                                // ← 逆序
cl   = multiply(newNegatedCostList(ret), -1)
temp = newNegatedCostList(空表)
mergeInplace(temp, cl, false)
return getLabels(temp)

源码注释承认了这个方案的缺陷：

我们退回到一个直白的合并方案，它偶尔会把步骤排错顺序，但 99% 的情况下结果是正确的。

要点：

差异 贪心段 回退段
顺序 优化后（按背包占用调度） 简单逆序，可能错序
合并相同配方 会（倍数累加） 不会（每步独立）
返回值 每步主产物标签 逆序标签求负再合并后的全部标签

recipeAsCostList 的符号

贪心段用来模拟「执行这一步后背包变成什么样」：

outC = negate(产物) × (-multiplier)   → 正（富余）
inC  = negate(原料) × (+multiplier)   → 负（消耗）
return mergeCostLists(inC, outC, false)

与 calculate() 主过程里 result 的构造顺序一致（先 outC 后 inC）， 源码里 recipeAsCostList 带了 // todo: unify with body of calculate() 注释， 承认两处逻辑重复。

相关条目