java - 最も可能な組み合わせに一致するアルゴリズム

Question

私は現在、マッチメイキング システムのアルゴリズムを書くのに苦労しています。数学について何か知っている人にとってはおそらくチャイルドプレイですが、私は知りません。

次の例を見てみましょう。

ロビーはちょうど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;
    }