基于球员等级和力量的优化队形的算法

Question

我想为一个假设的游戏创建一个算法，在这个游戏中，你可以用给定的玩家列表创建任意多的组。假设我有一个球员列表，其中每个球员都由他们的评分表示。

Given The following matrix

黄色的数字对应于任何给定组中的玩家数量。

白色的数字对应于组中每个玩家贡献的分数。

橙色中的数字对应于相应分数所需的评分阈值。

例如，如果我有一组评分为50,100的球员，使用矩阵可以确定他们每个人生成的分数为26.45，因为总评分为150，并且该组中有两名球员。那个队的总分是52.90分。

理想情况下，该算法将返回产生最佳分数的组，并限制我可以创建任意多个组，并且不需要将所有玩家放入组中。

什么是开始或解决此算法的好方法？

Answer 1

我会将这个问题归结为加权集合打包，并使用混合整数规划(MIP)解算器库，如OR-Tools。

对于可以组成一个组的每个玩家子集S，我们有一个变量x(S)，如果我们选择这个子集，变量x(S)为1，否则为0。我们将子集的得分设为score(S)，因此目标是最大化score(S) x(S)的总和。我们对每个玩家p都有一个约束: x(S)中包含p的所有S的和至多是1。

例如，如果三个玩家的所有非空子集都是可能的组，我们将得到

maximize score({1}) x({1}) + score({2}) x({2}) + score({3}) x({3}) +
score({1,2}) x({1,2}) + score({1,3}) x({1,3}) + score({2,3}) x({2,3}) +
score({1,2,3}) x({1,2,3})

subject to

x({1}) + x({1,2}) + x({1,3}) + x({1,2,3}) <= 1
x({2}) + x({1,2}) + x({2,3}) + x({1,2,3}) <= 1
x({3}) + x({1,3}) + x({2,3}) + x({1,2,3}) <= 1

x({1}), ..., x({1,2,3}) in {0, 1}

除非分数接近线性，否则现代硬件上的现代MIP解算器应该能够扩展到20个玩家。如果不是，还有更复杂的技术。