算法-尝试平衡团队技能水平，同时拥有相等数量的玩家 [英] Algorithm - Attempting to balance out team skill levels, while having a equal amount of players

问题描述

我有3支球队，他们有2名球员，3名球员和7名球员. 有18位球员坐在场边等待分配.

I have 3 teams, They have 2 players, 3 players and 7 players. There is 18 players sitting on the sidelines waiting to be assigned.

每个玩家都有自己的技能等级，这意味着等级1不会击败等级10.

Each player has their own skill level, meaning a level 1 is not going to defeat a level 10.

我想将每支球队平衡为10名球员.我想尽我所能使所有三支球队的技能达到同等水平.但是我不想删除团队中已经存在的球员.

I want to balance the teams out to 10 players each. And I want to try get all 3 teams as equal in skill as I can. But I don't want to remove the players already in a team.

但是我不确定如何实现这一目标. 我也不确定是否有简单的答案，或者计算起来是否昂贵.

But I'm not sure how I would accomplish this. I'm also not sure if there is a easy answer, or if this would be expensive to compute.

技能水平是我已经掌握的数字. 所有球队都有相等数量的球员.这意味着技能水平是唯一变化的数字.

The skill level is a number which I already have. The teams all have a equal amount of players. Which means the skill level is the only varying number.

一个例子是. 第1队有3名球员，总技术水平为4. 第2队有6名球员，总技术水平为8. 第3队有8名球员，总技术水平为9.

A example is. Team 1 has 3 players and a total skill level of 4. Team 2 has 6 players and a total skill level of 8. Team 3 has 8 players and a total skill level of 9.

我有13名需要分配的球员，所以每支球队都是10名球员. 而且我想尝试匹配所有技能水平.

I have 13 players who need to be assigned so the teams are 10 players each. And I want to try match up the total skill levels.

推荐答案

这对我来说就像您正在尝试将一组(多个)数字(技能水平")划分为大小相等的块(团队" )，以使平均值(总技能水平")尽可能接近相等.

This reads to me like you are trying to partition a (multi)set of numbers (the "skill levels") into blocks of equal size ("teams") so that the averages ("total skill level") are as close to equal as possible.

为解决这个问题，我将从计算平均技能水平开始，该平均技能水平是技能水平的总和除以玩家数量，然后将此数字称为s.如果总共有m个团队，每个团队都有k个玩家，总共有m*k个玩家，则每个团队的目标技能水平为k*s.

To solve this, I would begin by computing the average skill level, which is the sum of the skill levels divided by the number of players, call this number s. If there are to be m teams total, each with k players, giving a total of m*k players, then the target skill level for each teams is k*s.

由于您的团队已经部分填补，因此您基于示例的问题

Since your teams are already partially filled, the problem you have based on your example

我有3支球队，他们有2名球员，3名球员和7名球员.有 18名球员坐在场边等待分配.

I have 3 teams, They have 2 players, 3 players and 7 players. There is 18 players sitting on the sidelines waiting to be assigned.

是以下内容:

• A队，当前技能水平为a，需要8名球员，使得p1 + ... + p8 + a = 10*s
• B队，当前技能水平为b，需要7名球员，因此q1 + ... + q7 + b = 10*s
• 当前技能水平为c的C队需要3名球员，因此r1 + r2 + r3 + c = 10*s

• Team A, with current skill level a, needs 8 players such that p1 + ... + p8 + a = 10*s
• Team B, with current skill level b, needs 7 players such that q1 + ... + q7 + b = 10*s
• Team C, with current skill level c, needs 3 players such that r1 + r2 + r3 + c = 10*s

要获得强力解决方案，请先找到C队的球员，然后使用其余的球员解决A队和B队.

For a brute force solution, find the players for Team C first, then use the remaining players to solve for Teams A and B.

要获得更聪明的解决方案，您需要意识到这确实是一个子集总和问题 ，并使用一种著名的算法来解决该问题.我建议使用链接文章中介绍的动态编程解决方案.

For a more clever solution, you need to realize that this is really a subset sum problem, and use one of the well-known algorithms for solving that. I recommend the dynamic programming solution as described in the linked article.

这篇关于算法-尝试平衡团队技能水平，同时拥有相等数量的玩家的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！