algorithm - 我如何从一组项目中选择最有利的项目组合？

Question

我正在设计一款游戏，其中 AI 需要确定哪种盔甲组合将为角色提供最佳的整体统计奖励。每个角色将有大约 10 个属性，其中只有 3-4 个是重要的，而在那些重要的属性中，有几个会比其他的更重要。

护甲也会提升 1 项或所有属性。例如，一件衬衫可能会给角色+4 的智力和+2 的耐力，而同时，一条裤子可能只有+7 的力量，除此之外别无其他。

假设一个角色可以选择合适的盔甲(5 条裤子、5 副手套等)。我们指定智力和感知是该角色最重要的属性。我如何编写一个算法来确定哪种盔甲和元素组合会导致任何给定统计数据中的最高值(例如本例中的智力和感知)？

Answer 1

针对一项统计数据

这很简单。首先，一些假设:

• 你没有提到这一点，但大概一个人最多只能为特定插槽穿一种盔甲。也就是说，你不能穿两条裤子，也不能穿两件衬衫。

• 据推测，一件装备的选择也不会影响或与其他装备发生冲突(除了不能在同一个插槽中放置超过一件衣服的限制)。也就是说，如果你穿裤子，这绝不会妨碍你穿衬衫。但请注意，更微妙的是，我们假设您不会因佩戴两件相关元素而获得某种协同效应。

假设要针对统计量X，那么算法如下:

• 按位置对所有项目进行分组。
• 在每个组中，按照对 X 的提升程度降序排列该组中的潜在项目。
• 在每组中挑选第一个并穿上它。
• 所选的项目集是最佳装载量。

证明:获得更高 X 统计数据的唯一方法是，如果有一个项目 A 比其组中的其他项目提供更多 X。但是我们已经对每个组中的所有项目进行了降序排序，所以不可能有这样的A。

如果违反假设会怎样？

• 如果第一个假设不成立——也就是说，你可以在每个插槽中佩戴多件元素——那么不是从每组中挑选第一个元素，而是挑选第一个 <来自每个组的 em>Q(s) 个项目，其中 Q(s) 是可以放入插槽 s 的项目数。

• 如果假设二不成立——也就是说，项目确实相互影响——那么我们没有足够的信息来解决这个问题。我们需要具体了解项目如何相互影响，或者被迫通过暴力尝试所有可能的项目组合，看看哪些组合的总体结果最好。

---

针对N个统计

如果您想同时针对多个统计数据，则需要一种方法来判断某项数据“有多好”。这称为适应度函数。您需要确定 N 个统计数据相对于彼此的重要性。例如，您可能决定感知每 +1 值 10 点，而智力每 +1 值仅值 6 点。您现在有一种方法可以评估项目相对于彼此的“优劣”。

一旦你有了它，你就可以优化适应度函数 F，而不是针对 X 进行优化。然后这个过程和上面的一个统计是一样的。