按两个因素对人进行分组的算法

Question

这个问题我想了很久，还是想不通。我正在寻找一种算法(使用任何语言)按照以下这两条规则对一群人进行分组:

1. 按由数字表示的技能水平升序分组(技能越高越熟练)。在可能的情况下，小组中最好和最弱的人之间的差距不应超过 1 分。
2. 尽可能分散来自同一国家/地区的人，即不要将来自同一国家/地区的人放在同一组中，同时不要违反上述规则 1。在可能的情况下，一个小组不应由来自一个国家/地区的人组成。

每组最多可容纳 4 人(如果可能)或 3 人，例如如果有 18 个人，则将他们分成 3 组，每组 4 人和 2 组，每组 3 人。

样本数据(技能水平后跟国家):

• 5 美国
• 5 美国
• 5 美国
• 5 美国
• 6GB
• 6GB
• 6GB
• 7CN
• 7CN
• 7CN
• 7CN
• 7 香港
• 8 美国
• 8 美国
• 8 美国
• 8 CA
• 8 中国
• 8 中国

..被分成2组4s和2组3s

有什么想法请帮忙？提前谢谢你

Answer 1

我会提出以下建议。

首先，按国家和技能水平汇总数据，因此数据看起来更像:

US    5    4
GB    6    3
. . .

按最高排名排序。

然后使用贪心算法。

• 确定组中的成员数量(大小或大小 - 1)
• 从第一组中选出一个(排名最高的)。
• 继续从满足国家/地区条件的每个后续组中取一个(因此您可能需要跳过美国)。

这定义了第一组。

然后重复。

这不能保证是最佳的。但是话又说回来，没有为问题定义最优性。哪个更重要？国家多样性还是技能相同？