提问人：Astudent 提问时间：9/16/2021 最后编辑：Astudent 更新时间：9/16/2021 访问量：172
基于球员评级和实力优化团队阵型的算法
Algorithm to optimize a team formation based on player rating and power
问：
我想为一个假设的游戏创建一个算法，您可以在其中使用给定的玩家列表创建任意数量的组。 假设我有一个球员列表，其中每个球员都由他们的评分表示。
黄色数字对应于任何给定组中的玩家数量。
白色的数字对应于小组中每个玩家贡献的分数。
橙色中的数字对应于相应分数所需的评级阈值。
例如，如果我有一组评分为 [50， 100] 的球员，使用矩阵可以确定他们每个人的得分为 26.45，因为总评分是 150，并且该组中有两名球员。该团队的总得分是52.90。
理想情况下，该算法将返回获得最佳分数的组，并具有我可以根据需要创建任意数量的组的约束，并且并非所有玩家都需要被放在一个组中。
开始或解决此算法的好方法是什么？
答：
0赞
David Eisenstat
9/16/2021
#1
我会将此问题简化为加权集打包，并使用混合整数程序 （MIP） 求解器库，例如 OR-Tools。
对于可以组成组的每个玩家子集 S，我们有一个变量 x（S），如果我们选择子集，则为 1，否则为 0。我们让子集的分数为 score（S），因此目标是最大化 score（S） x（S） 的 S 之和。我们对每个玩家 p 都有一个约束：包含 x 的 p（S） 的所有 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 名玩家。如果没有，则有更复杂的技术。
评论