java 匈牙利算法 任务分配

匈牙利算法是一种用于解决任务分配问题的算法，它可以找到一种最优的任务分配方案，使得支付的报酬总数最小。该算法的基本思想是通过不断调整任务分配的方式，使得每个人都能得到最适合自己的任务，并且使得总的报酬最小。

下面是使用Java实现匈牙利算法解决任务分配问题的示例代码：

import java.util.Arrays;

public class HungarianAlgorithm {
    private static int N;
    private static int[][] costMatrix;
    private static int[] matchX;
    private static int[] matchY;
    private static boolean[] visited;

    public static int findMinCost(int[][] cost) {
        N = cost.length;
        costMatrix = cost;
        matchX = new int[N];
        matchY = new int[N];
        Arrays.fill(matchX, -1);
        Arrays.fill(matchY, -1);

        for (int i = 0; i < N; i++) {
            visited = new boolean[N];
            dfs(i);
        }

        int minCost = 0;
        for (int i = 0; i < N; i++) {
            minCost += costMatrix[i][matchX[i]];
        }

        return minCost;
    }

    private static boolean dfs(int x) {
        for (int y = 0; y < N; y++) {
            if (!visited[y] && costMatrix[x][y] == 0) {
                visited[y] = true;
                if (matchY[y] == -1 || dfs(matchY[y])) {
                    matchX[x] = y;
                    matchY[y] = x;
                    return true;
                }
            }
        }
        return false;
    }
}

// 使用示例
public class Main {
    public static void main(String[] args) {
        int[][] costMatrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        int minCost = HungarianAlgorithm.findMinCost(costMatrix);
        System.out.println("最小报酬总数为: " + minCost);
    }
}

这段代码中，我们首先定义了一个`HungarianAlgorithm`类，其中的`findMinCost`方法接受一个二维数组`cost`作为输入，表示任务之间的报酬矩阵。然后，我们使用匈牙利算法来计算最小报酬总数，并返回结果。

在`Main`类中，我们创建了一个示例的报酬矩阵`costMatrix`，然后调用`HungarianAlgorithm`类的`findMinCost`方法来计算最小报酬总数，并将结果打印出来。