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