一件装备可能同时占用两个位置。按单件分数从高到低挑选,有时会阻止两件总分更高的装备同时使用,因此需要检查组合约束。
固定规则与输入
本例有五个装备位置、八件候选物品,每件声明占用位置和实用分。任何位置最多被一件物品占用,允许留空,目标是所选物品分数相加最大。
物品0:位置[2],分23 物品1:位置[1, 3],分9 物品2:位置[2],分18 物品3:位置[1, 4],分19 物品4:位置[0, 1, 3],分17 物品5:位置[0],分17 物品6:位置[3, 4],分5 物品7:位置[0, 4],分18
逐步观察结果
物品0占用[2],分数23,选入本例最优组合True。它与其他已选物品的位置完全不重合。
物品1占用[1, 3],分数9,选入本例最优组合False。未选入不代表单件无用,而是需要服从整体组合。
物品2占用[2],分数18,选入本例最优组合False。未选入不代表单件无用,而是需要服从整体组合。
物品3占用[1, 4],分数19,选入本例最优组合True。它与其他已选物品的位置完全不重合。
物品4占用[0, 1, 3],分数17,选入本例最优组合False。未选入不代表单件无用,而是需要服从整体组合。
物品5占用[0],分数17,选入本例最优组合True。它与其他已选物品的位置完全不重合。
物品6占用[3, 4],分数5,选入本例最优组合False。未选入不代表单件无用,而是需要服从整体组合。
物品7占用[0, 4],分数18,选入本例最优组合False。未选入不代表单件无用,而是需要服从整体组合。
包含空集合在内共33个可行集合。最高分59,共有1个同分最优集合,本例选取[0, 3, 5]。按单件分数贪心选择[0, 3, 5],合计59分。
独立复核
逐个候选集合检查占用是否相交。最优组合未必件数最多;列出可行组合的数量、最佳分和最佳集合,可以区分搜索完整性与某一个答案可行性。
复核时先保留本例输入,再自己写出中间状态。若结果不同,应从最早出现差异的位置检查,尤其留意边界是否包含、索引从哪里开始、取整何时发生,以及是否使用了尚未更新的旧状态。计算得到的结论仅适用于已经说明的规则,修改规则后需要重新验证。
适用范围
分数只是自定评价,不代表真实游戏中的强度。套装效果、负重、角色限制或特殊联动都未计入;增加这些规则后应重新判断组合,不能沿用这里的简单相加结论。
