获取瓷砖组合的最大分数（Java，优化问题）

Question

我有一张地图，整数>。 Tuple 表示两个不同 Tiles 之间的连接（整数是 Tiles 的 ID），地图的值是每个连接值得的点。

因此，例如条目 <5,3>, 7 表示图块 5 和图块 3 之间的连接值得 7 分。 每个图块可以是不同连接的一部分，因此另一个可能的条目是 <5,13>, 4.

我想计算连接的最大点数，但我只能使用每个图块一次。 例如，如果我使用连接 5,3（7 点），我就不能使用 5,13。 你能帮我设计一个算法来检查每个可能的组合并返回最大可能的点吗？

我已经尝试提示 ChatGPT 解决该问题，但该算法没有按预期工作:(

Answer 1

ChatGPT 的这段代码工作得很好，我想问题已经解决了^^

int maxPoints(Map<Tuple<Integer, Integer>, Integer> connections) {
Set<Integer> usedTiles = new HashSet<>();
return explore(connections, usedTiles);
}

int explore(Map<Tuple<Integer, Integer>, Integer> connections, 
Set<Integer> usedTiles) {
int maxPoints = 0;
for (Map.Entry<Tuple<Integer, Integer>, Integer> entry : 
connections.entrySet()) {
    Tuple<Integer, Integer> connection = entry.getKey();
    int tile1 = connection.first;
    int tile2 = connection.second;
    int points = entry.getValue();
    
    if (!usedTiles.contains(tile1) && !usedTiles.contains(tile2)) {
        // Add points and tiles to used set
        usedTiles.add(tile1);
        usedTiles.add(tile2);
        int remainingPoints = points + explore(connections, usedTiles);
        maxPoints = Math.max(maxPoints, remainingPoints);
        
        // Backtrack
        usedTiles.remove(tile1);
        usedTiles.remove(tile2);
    }
}
return maxPoints;

}