我目前正在努力为我的匹配系统编写算法。对于那些对数学一知半解的人来说，这可能是儿童读物，嗯，我不知道。
让我们举以下例子：
大厅由恰好8名玩家组成
队列中有9个参与方。聚会规模为：1、6、3、8、2、1、5、3、2。
算法需要在这些聚会中创建尽可能多的完整大厅。
可能只有满座的大厅。因此，可能会有无法匹配的政党。然后，他们将等待新的派对排队。
我目前的代码确实将各方与游说团相匹配，但它缺乏找到最佳组合以找到尽可能多的完整游说团的功能。
示例：大厅大小正好为7，聚会：2,2,4,3,1,5->2,5和4,3可以匹配，但它会匹配2,2,3和4,1,5不能匹配。
我非常感谢任何帮助。
我当前的代码：
// Limitation: Is not intelligent. Example: Size 7, Teams 2,2,4,3,1,5 -> 2,5 and 4,3 could be matched, but it will do 2,2,3 and 4,1,5
// Possible solution: Sort for size or match parties with lowest possible match e.g try 5,1 then 5,2 ...
public List<MatchedParty> getLobbies(List<Party> parties, int teamSize) {
List<MatchedParty> lobbies = new ArrayList<>();
parties.sort(Comparator.comparing(Party::getJoinedQueueTime));
while (!(parties.isEmpty())) {
MatchedParty matchedParty = new MatchedParty();
List<Party> team1 = new ArrayList<>();
List<Party> team2 = new ArrayList<>();
boolean teamReset = false;
int counter = 0;
while (team1.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize || team2.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize) {
if (team1.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize) {
team1.clear();
}
if (team2.stream().mapToLong(c -> c.getMembers().size()).sum() != teamSize) {
team2.clear();
}
// Iterate over all parties and add matching ones to the teams
for (int i = counter; i < parties.size(); i++) {
if (team1.stream().mapToLong(c -> c.getMembers().size()).sum() + parties.get(i).getMembers().size() <= teamSize && !(team2.contains(parties.get(i)))) {
team1.add(parties.get(i));
} else if (team2.stream().mapToLong(c -> c.getMembers().size()).sum() + parties.get(i).getMembers().size() <= teamSize && !(team1.contains(parties.get(i)))) {
team2.add(parties.get(i));
}
}
// Reset search when first team is full
if ((team1.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize || team2.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize) && !(teamReset)) {
counter = 0;
teamReset = true;
}
// Check if we iterated over all parties, if so exit the loop
if (counter <= parties.size()) {
counter++;
} else {
break;
}
}
// Are there still teams found? If not, return the lobbies
if (team1.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize && team2.stream().mapToLong(c -> c.getMembers().size()).sum() == teamSize) {
matchedParty.setTeam1(team1);
matchedParty.setTeam2(team2);
lobbies.add(matchedParty);
parties.removeAll(team1);
parties.removeAll(team2);
} else {
return lobbies;
}
}
// Maybe all parties found a team, if so return too
return lobbies;
}
你的算法通常是正确的，但你可以做一个改进。由于你只关心对给定的参与方大小进行精确匹配，我会将每个参与方映射到一个列表中，该列表包含给定大小的所有参与方：IE:{1: [parties of size 1], 2: [parties of size 2], ...}
然后看看这个：
https://en.wikipedia.org/wiki/Partition_%28number_theory%29
棘手的是，我们希望尽可能完美地匹配事物。基本上，我们希望从最少的政党开始，到需要合并的最多政党。聚会大小为8的IE：8, 7 + 1, 6 + 2, 5 + 3等等。一旦这些都匹配了，我们就看需要组合3个聚会的聚会(总是按照从大到小的顺序(：6 + 1 + 1, 5 + 2 + 1, 4 + 2 + 2...，然后是有4个部分的聚会，然后是5个部分、6个部分、7个部分，最后是8个部分(全部(。
看起来有22个分区，每个分区有8个，您可能只是对它们进行硬编码并在它们上循环。根据您的最大参与方数量，您可以为所需的所有参与方构建分区表。
以下是该算法在示例列表中的大致工作方式：
1, 6, 3, 8, 2, 1, 5, 3, 2
{party size: number of parties remaining}
{8: 1, 6: 1, 5: 1, 3: 2, 2: 2, 1: 1}
{6: 1, 5: 1, 3: 2, 2: 2, 1: 1} => (8)
{5: 1, 3: 2, 2: 1, 1: 1} => (8), (6,2)
{3: 1, 2: 1, 1: 1} => (8), (6,2), (5,3)
{3: 1, 2: 1, 1: 1}
如果您关注剩余参与方的总数，您将停止检查是否存在3 + 2 + 1 = 6 < 8，因此无法创建任何其他有效参与方。我相信这创造了派对的想法数量。
你打算举办7人聚会的例子：
2,2,4,3,1,5
{5: 1, 4: 1, 3: 1, 2: 2}
{4: 1, 3: 1, 2: 1} => (5,2),
{2: 1} => (5,2),(4,3)
同样，在这一点上，不可能让7成为一个政党。
至于生成分区，这似乎是可靠的：
https://www.geeksforgeeks.org/generate-unique-partitions-of-an-integer/
是否需要优化取决于最大聚会规模。16有231分区，但32有8349仍然不错，但是64有1741630，这可能很糟糕，除非你有很多聚会。http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Partitions/partitions.html#pcalc1
编辑：这里唯一的问题是小党派可能处于不利地位。在这种情况下，您可能会颠倒搜索顺序，因此它开始查看最小大小(全部(的聚会，而不是最小大小(完整聚会(。我可能每次都会颠倒搜索顺序，比如3-10次搜索。取决于你多久做一次。
你可能还想尝试两个方向，然后选择一个效果更好的方向。
按相反顺序：
1, 6, 3, 8, 2, 1, 5, 3, 2
{8: 1, 6: 1, 5: 1, 3: 2, 2: 2, 1: 1}
{8: 1, 6: 1, 5: 1, 3: 1} => (1,2,2,3)
{6: 1} => (1,2,2,3),(3,5),(8)
虽然在这种情况下，两种方式都创建了3个完整的组，但我怀疑情况是否会一直如此。然而，请注意，这种方法确实将其减少到只有一个6人的政党，而不是3人、2人和1人的政党。
这种做法基本上是为了尽可能减少缔约方的数量。另一种方法旨在最大限度地增加完整小组的数量。两者都有各自的用途，建议你同时使用，只是你使用其中一种与另一种的频率问题。
嗯，第三种选择可能是从两边攻击它，尽管在这种情况下，你有其他问题，它对在中间的人有偏见。
1, 6, 3, 8, 2, 1, 5, 3, 2
{8: 1, 6: 1, 5: 1, 3: 2, 2: 2, 1: 1}
{6: 1, 5: 1, 3: 2, 2: 2, 1: 1} => (8)
{6: 1, 5: 1, 3: 1} => (8),(1,2,2,3)
{6: 1} => (8),(1,2,2,3),(5,3)
实际上，如果你想让事情变得更有趣，你可以随机打乱所有分区，并以这种方式运行算法，尽管怀疑这会产生高于平均水平的结果。要点是N的整数分区是你需要关注的
因此，在阅读了评论者的几个链接后，@Andreas的答案似乎是最正确的。我的问题似乎是垃圾箱包装问题的一个变体，只是在我的情况下，我确实需要只装满垃圾箱。
我的问题主要可以通过使用我在问题中发布的算法来解决，但将所有条目从最高到最低排序，在填充大厅(垃圾箱(时，首先插入最大的条目。