最优兑换卡组合-KM算法
1 问题概述
用户下了一笔订单，订单中有 x 件商品，y 张兑换卡，兑换卡使用在不同商品上，优惠金额不同，限制 1 件商品只能使用 1 张兑换卡，选取 x 与 y 的组合，使得优惠金额最大。
2 技术方案
2.1 朴素算法
优先选择 兑换卡与商品 中优惠金额最大的选项（这里需要先排序），目的让每个商品与券的组合尽可能是最优解。很明显，这种思路只能确保当前选取最优选项，例如以下反例：
如图，按照算法思路，只能取到两张兑换卡，优惠总额 22 元
- 选取 兑换卡1-商品B 优惠金额 16 元
- 选取 兑换卡2-商品C 优惠金额 6 元
- 导致兑换卡3无法被选用
而这个例子的最优选项为【兑换卡1-商品A，兑换卡2-商品C，兑换卡3-商品B】，优惠总额为 23 元。
2.2 暴力枚举
枚举所有方案，相当于求组合方案，时间复杂度高达 O(n!)，若按照 1s 钟计算机能运行 10^8 次计算这样的标准，当 n = 13 的时候，需要超过 10s 才能得到答案，并且 n 每增加 1，时间就会扩大 n 倍。
这里给一份简洁的求组合方案算法，用于参考：
public class Combination {
int n, m;
int[] A;
public Combination() {
n = 100;
m = 20;
A = new int[m];
Search(0);
}
void Search(int k) {
if (k == m) {
for (int a : A) System.out.print(a);
System.out.println();
return;
}
for (int i = (k > 0) ? A[k - 1] + 1 : 1; i <= n; i++) {
A[k] = i;
Search(k + 1);
A[k] = 0;
}
}
public static void main(String[] args) {
Combination t = new Combination();
}
}
2.3 KM算法（二分图最优匹配算法）
2.3.1 km（Kuhn-Munkres）算法简介
KM 算法是一种二分图最佳匹配算法，该算法主要用于解决一个经典的问题模型：完美婚姻问题。该问题的描述如下：n 个男生和 n 个女生相亲，第 i 个男生和第 j 个女生在一起的幸福值是 val(i, j)，如何让 n 个男生和 n 个女生完成一一配对，使得这个整体的总幸福值最大。
如果还不了 KM 算法，可以先阅读第 3，4 节，再回到这里看解决方案。
我们的场景和完美婚姻问题类似，并且 KM 算法的时间复杂度是 n^3，且能求出哪张商品用于哪张兑换卡。
我们把商品当作女生，兑换卡当作男生，商品 i 使用兑换卡 j 的优惠金额是 W(i,j) 去构建二分图，如果商品 i 不能使用兑换卡 j，则优惠金额设为零，以此方式，我们会遇到一些问题：
2.3.2 如何满足 KM 算法的使用条件？
因为 KM 算法是用于求解二分图的最优匹配，所以二分图必须存在最优匹配才能使用 KM 算法求解。存在最优匹配的必要条件：必须两边的点相同，且至少存在一种匹配方案使得所有点被匹配。所以我们需要补点和补边。
补边策略：将不存在的边，权重设为零。
补点策略：将不存在的点，与其他对应顶点权重设为零。
2.3.3 代码实现
import com.google.common.collect.Sets;
import lombok.AllArgsConstructor;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
public class ExchangeCard {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("商品1", "A", 15));
items.add(new Item("商品2", "B", 15));
items.add(new Item("商品3", "C", 15));
List<Coupon> coupons = new ArrayList<>();
coupons.add(new Coupon("兑换卡1", 5, Sets.newHashSet("B")));
coupons.add(new Coupon("兑换卡2", 5, Sets.newHashSet("B")));
coupons.add(new Coupon("兑换卡3", 5, Sets.newHashSet("A", "B", "C")));
long thisTime = System.currentTimeMillis();
KuhnMunkres km = buildKMParam(items, coupons);
km.maxMatching();
int maxMatch = 0;
System.out.println("匹配结果：");
for (int couponIndex = 0; couponIndex < km.getN(); couponIndex++) {
if (km.getMatch()[couponIndex] != -1) {
// System.out.println("左边顶点 " + km.getMatch()[couponIndex] + " 匹配右边顶点 " + couponIndex);
int itemIndex = km.getMatch()[couponIndex];
// 剔除虚拟节点
if (itemIndex > items.size() - 1 || couponIndex > coupons.size() - 1) {
continue;
}
Item item = items.get(itemIndex);
Coupon coupon = coupons.get(couponIndex);
if (!coupon.itemCodes.contains(item.itemCode)) {
continue;
}
maxMatch += item.price - coupon.cost;
System.out.println(item.identify + "选择" + coupon.code);
}
}
System.out.println("优惠值：" + maxMatch);
System.out.println("耗时：" + (System.currentTimeMillis() - thisTime));
}
public static KuhnMunkres buildKMParam(List<Item> items, List<Coupon> coupons) {
int itemsLength = items.size();
int couponsLength = coupons.size();
// int n = itemsLength + couponsLength;
int n = Math.max(itemsLength, couponsLength);
int[][] love = new int[n][n];
// 补边 & 补点
for (int i = 0; i < n; i++) {
Coupon coupon = i > couponsLength - 1 ? null : coupons.get(i);
for (int j = 0; j < n; j++) {
Item item = j > itemsLength - 1 ? null : items.get(j);
if (coupon == null || item == null || !coupon.itemCodes.contains(item.itemCode)) {
love[j][i] = 0;
} else {
// 正常边
love[j][i] = item.price - coupon.cost;
}
}
}
return new KuhnMunkres(love);
}
@AllArgsConstructor
public static class Item {
String identify; // 商品行唯一标识
String itemCode; // 商品编码
Integer price; // 身份价
}
@AllArgsConstructor
public static class Coupon {
String code; // 券码
Integer cost; // 用券成本
Set<String> itemCodes; // 可用券商品集合
}
}
3 匈牙利算法
匈牙利算法是解决匹配问题的。网上有一篇很火的文章：用男女配对的例子，说明匈牙利算法的核心思想。
学习这个算法需要先从一些基本概念开始。
3.1 二分图
【定义】图论中的一种特殊模型。若能将无向图 G=(V,E) 的顶点 V 划分为两个交集为空的订单集，并且任意边的两个端点都分属于两个集合，则称图G为一个为二分图。
【解释】一张图要是二分图，需要满足以下几个要求：
- 无向图。意思是，一旦 AB 俩人有连线，就说明俩人相互喜欢，配对成功，不存在 A 单方面喜欢 B 的情况。
- 交集为空。意思是，男的是一个集合，女的是一个集合。不存在男生集合里混入女生的情况。
- 任意边的两个端点分属于两个集合。意思是，男的只能和女的配对。任何男的不能和男的配对，任何女的不能和女的配对。
满足上述条件就是二分图。
3.2 匹配
【定义】在 G 的一个子图 M 中，M 的边集中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
【解释】结合情侣配对问题，男生女生之间互生情愫的有很多，甚至有的人对多个人都有意向，因此潜在的情侣组合方式有很多种。所谓的“任意两条边都不依附于同一个顶点”，意思就是只要我们撮合的时候，不要给某个人安排两个对象就行。作为牵线人，我们可以撮合一对，也可以撮合两对，这样每一种撮合方式，都叫一个匹配。撮合成功的这些情侣就是所谓的子图M。
3.3 最大匹配
按照上面的撮合方式，我们既不能把没有意向的两个人撮合在一起，有的人又对多个人有意向，因此可以花一点心思，尽可能地协调一下大家的意向，做到多撮合成功几对。这样，成功撮合的情侣最多的这种撮合方式，就叫最大匹配。
3.4 最优匹配/完美匹配
如果非常幸运，在我们的安排下，每个人都找到了自己心仪的对象。这种撮合方式，叫做最优匹配或完美匹配。
3.5 交替路和增广路
交替路和增广路是用来解决新配对的时候发生冲突的问题。这里要结合具体问题解释才能更清楚。那么我们来结合具体问题，看看这个交替路和增广路有啥用处。
考虑一个下面这个二分图，怎么找到最大的匹配呢？
一个自然的思路是，一个一个的配对。首先给 A 配对。一看 A 和 a 有意向，那就先把他俩撮合到一起。
如图，蓝色的是他们本身有意向的情况，就是原始二分图，注意这里蓝线连一块叫“非匹配边”。红色的是我们给他们配对了，红线才叫“匹配边”。
好了，A 的问题暂时性解决了，轮到 B 了。结果 b 也想和 a 配对。
这时候，谁才能和 a 在一起呢？交替路和增广路就是解决这个冲突的。
这时候，我们要找一条交替路，就是依次经过非匹配边（蓝线）、匹配边（红线）。那么我们从B出发，开始找交替路了。
B 和 c 都是没有被匹配过的点，而它又是这条交替路的起点和终点。这条交替路就是增广路。
现在我们要做一个取反操作，将上面这条增广路的匹配边变成不匹配边，不匹配边变成匹配边。
还是用红色表示匹配边，蓝色表示非匹配边。画在图上，现在的匹配变成这样。
然后，我们发现，刚刚的冲突问题解决了。由 B 和 a 在一起，A 和 c 在一块。
增广路是怎么解决冲突问题？
增广路的核心特点就是 “起点终点都是非匹配点” ，这样就导致非匹配边比匹配边多了一条。增广路建立连接时，必须建立在两者有意向的基础上。这样我们取反，也就是交换匹配和非匹配边的身份。我们就多得到了一条匹配边。这个取反的过程，就是把原本匹配上的两个人拆散，给第三个人腾位置。
AB 的问题都解决了，轮到 C 了。C 要和 c 配对，又发生冲突了。于是，又要使用增广路来增加一个匹配了。
取个反得到：
画成图长这样：
现在，ABC 的配对都解决了。我们找到了最大匹配。由于 A\B\C\a\b\c 都找到了自己的心仪对象。因此，这个最大匹配也是完美匹配。
下面这个链接里的二分图，就没能找到完美匹配。
上述利用增广路找最大匹配的算法，就叫做匈牙利算法。
总结一下匈牙利算法：
每个点从另一个集合里挑对象，没冲突的话就先安排上，要是冲突了就用增广路径重新匹配。重复上述思路，直到所有的点都找到对象，或者找不到对象也找不到增广路。
3.6 深度优先和广度优先
上述是深度优先匈牙利算法。就是冲突了立刻用增广路来解决。
另外一种是广度优先匈牙利算法。思路是，冲突了就换一个心仪对象，看另一个心仪对象是不是也配对了，要是都配对了，再用增广路来解决。
广度优先的流程是这样的：
（1）A 和 a 连上。
（2）B 也想连 a，但是 a 被连了，就找下一个心仪对象 b。
（3）b 没有被连上，B 和 b 就连在一起。
（4）轮到 C 的时候，C 找心仪对象 c。
（5）c 也没被连上，所以 C 和 c 连一起。
3.7 代码实现
代码上我们通常用深度优先算法，因为深度优先算法在代码上好实现。
二分图的体现（graph）：
在匈牙利算法中，二分图通常表示为两组顶点，分别为左侧顶点和右侧顶点，以及它们之间的边。
在二维数组中，通常将左侧的顶点表示为行，右侧的顶点表示为列，数组中的值表示两个顶点之间是否存在边。
对此我们可以将文中案例的二分图转换为以下结构：
int[][] graph = {
{1, 0, 1}, // 用于表示：文中左侧顶点 A 与右侧顶点 a, c 的关系
{1, 1, 1}, // 用于表示：文中左侧顶点 B 与右侧顶点 a, b, c 的关系
{0, 0, 1}, // 用于表示：文中左侧顶点 C 与右侧顶点 c 的关系
};
考虑从左侧顶点 u 开始出发找到增广路（maxMatching）：
private int maxMatching() {
Arrays.fill(match, -1); // 初始化男生匹配状态 -1：未匹配
int result = 0;
int m = graph[0].length;
for (int u = 0; u < n; u++) {
// 创建一个 visited 数组，用来标记哪些右侧顶点在 dfs 递归中被访问过
// 作用：确保不会再同一次 dfs 递归中多次访问同一个右侧顶点，以此避免形成环路
visited = new boolean[m];
// 寻找增广路
if (dfs(u)) {
result++;
}
}
return result;
}
实现寻找增广路的算法（DFS）：
private boolean dfs(int u) {
int m = graph[0].length;
for (int v = 0; v < m; v++) {
// 存在左边顶点 u 到右边顶点 v 的边 && 右侧顶点 v 没有被访问过（前面提到的避免形成环路）
if (graph[u][v] == 1 && !visited[v]) {
visited[v] = true; // 右侧顶点 v 标记被访问
// 如果右侧顶点 v 还未与任意左侧顶点匹配 || 能从右侧顶点 v 出发匹配到增广路径
if (match[v] == -1 || dfs(match[v])) {
match[v] = u; // 能匹配到增广路径，将左侧顶点 u 与右侧顶点 v 进行匹配
return true;
}
}
}
return false;
}
完整代码实现：
import java.util.Arrays;
public class HungarianDFS {
public static void main(String[] args) {
int[][] graph = {
{1, 0, 1},
{1, 1, 1},
{0, 0, 1},
};
HungarianDFS hungarianDFS = new HungarianDFS(graph);
int maxMatch = hungarianDFS.maxMatching();
System.out.println("最大匹配数：" + maxMatch);
System.out.println("匹配结果：");
for (int v = 0; v < graph[0].length; v++) {
if (hungarianDFS.match[v] != -1) {
System.out.println("左边顶点 " + hungarianDFS.match[v] + " 匹配右边顶点 " + v);
}
}
}
private int[] match;
private boolean[] visited;
private int[][] graph;
public HungarianDFS(int[][] graph) {
this.graph = graph;
int m = graph[0].length;
match = new int[m];
}
private int maxMatching() {
Arrays.fill(match, -1);
int result = 0;
int n = graph.length;
int m = graph[0].length;
for (int u = 0; u < n; u++) {
visited = new boolean[m];
if (dfs(u)) {
result++;
}
}
return result;
}
private boolean dfs(int u) {
int m = graph[0].length;
for (int v = 0; v < m; v++) {
if (graph[u][v] == 1 && !visited[v]) {
visited[v] = true; // 右侧顶点 v 标记被访问
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}
}
输出结果：
最大匹配数：3
匹配结果：
左边顶点 0 匹配右边顶点 0
左边顶点 1 匹配右边顶点 1
左边顶点 2 匹配右边顶点 2
4 KM 算法
4.1 KM 算法解决什么问题
最大匹配不是唯一的，不同人用匈牙利算法，可能找到不同的匹配结果。那么怎么评估这些不同的匹配呢？还是拿情侣配对举例子，一种评价方法就是，看情侣彼此的满意程度。比如，有的人当媒人，介绍的每一对情侣都极其满意，有的人当媒人，虽然把情侣都凑在了一起，介绍的每一对情侣只是略微有意向，但是没和最喜欢的在一起。
这个喜欢程度，就是给原本的二分图，加了一个权重。
在权重的前提下，该如何寻找最优匹配，且使得权重最大呢？KM算法就是为了解决这个问题的。
4.2 权重问题的转化
我们知道匈牙利算法能解决最大匹配问题，现在加了权重，KM 算法就是想了个办法，将问题转换成了匈牙利算法可以解决的形式。
现在二分图带了权重，可以理解为加了一种约束，这种约束让我们优先选择那些权重大的边出来，进行匹配。
因此我们要先把权重最大的边都挑出来，学术一点，就是挑一个子图出来。因为我们挑出来的都是权重最大的边，我们只要在这个子图中，找到最大匹配，这个最大匹配一定是权重最大的（很重要，意思就是这个子图里，在上面随便找都是权重最大的匹配，这样我们就能用匈牙利算法解决问题了）。 流程就是：
但这里有一个问题，我们都找最大权重的边组成的子图，这个子图很小，很容易冲突。形象来说，大家找对象的要求都太高了，很可能会没法满足他们的要求。众所周知，找不到对象是很惨的，因此对象还是得找的。这时候只能委屈一部分人，让他稍微降低标准，让他从别的人里挑对象。因此目前的流程变成了：
这个KM算法的流程，核心思想就是：优先选择最满意的，因为要求太高找不到对象的那些人，降低标准扩大择偶范围，直到找到对象为止。
KM算法对择偶的3大启示：先下手为强（优先选择），广撒网（更多连接），认清自己几斤几两（降低标准）
这个问题中，找最大匹配的那一部分我们会了，用匈牙利算法就能搞定。剩下就是两个问题了：
- 如何找到这个所谓的“权重最大的子图”。
- 怎么稍微扩大择偶范围（既不能降得太低，也不能不降）。
上述两个问题，就是 KM 算法的精髓。
这个权重最大的子图，就是“相等子图”。扩大择偶范围，就是“顶标的更新---建立新的相等子图”的过程。
要注意的是，上面说的权重最大，并不是整个图的范围内权重越大越好，而是目前能力范围内我们能选的最大的权重边（毕竟有些人需要降低标准才能找到对象）。
接下来就要讲如何解决上面提出的两个问题。
4.2 问题1：如何寻找“权重最大的”子图？
首先强调一点，我们的这个子图的目的，是为了实现一个效果：
在这个子图上，不考虑权重找到最大匹配 等价于 在带权重的图上找权重最大的最大匹配。
我们挑一伙人出来，这些人彼此的满意度都比较高，那些低的暂时不考虑。在这伙人里找对象。找不到了再考虑加人进来。
为了实现这个目标，我们给每个人增加一个顶标。顶标是我们决定一条边是否加入子图的依据。顶标可以理解为择偶的最高标准，如果双方的适配程度达到了这个最高标准，就加入到择偶范围内来，就是加入到子图中。
比如说小王择偶的最高标准是 Swang，小李择偶最高标准Sli。小王和小李的喜欢程度是 W（即二分图中，小王和小李的连线权重），若 Swang +Sli =W，小王和小李的连线就加入子图中，进入择偶候选人范围。注意到上面这个等式，于是这样选出来的子图，叫做相等子图。
然而这个最高标准，是不断变化的。也就是下一个问题，如何不断地调整最高标准，让择偶范围不断变化。
4.3 问题2：如何扩大择偶范围
我们这里拿一个具体的例子来看。
这里有 5 个女生 x1-x5， 5 个男生 y1-y5。他们之间为 0 就是没有连线，大于 0 的数是权重，就是他们相互喜欢的程度。
第一步，最高标准初始化。
需要注意的是，我们是一个无向的二分图，意思就是权重是双方共同的喜欢程度，因此可以选一个人作为代表就行了。于是，我们让女生做单方面的选择。男生们的顶标都设为0。
一开始女生们都想找最喜欢的对象，我们将她们的最高标准都设为她们最喜欢的那个。比如，x1 对所有男生都有意向，喜欢程度分别是 3,5,5,4,1。那小王目前的最高标准就是 5。
在第一次选择中，y2、y3加入择偶范围，其他三人暂不考虑。所有女生都这样，选出自己最喜欢的加入择偶范围。
我们就得到了子图：
这样的好处就是，这样挑出来的子图中，彼此喜欢程度一定是最大的。这样我们就不用考虑权重的问题了，问题就变成了一个在局部子图上，挑选最大匹配的问题，就可以用匈牙利算法解决了。
接下来，我们就用匈牙利算法来给她们分配对象。红线表示匹配好了。
x1 和 x2 都成功找到了对象。但是 x3 也愿意和 y2 一起。冲突了。一开始有了矛盾，我们先用匈牙利算法给她们尝试解决一下。
我们找到一条增广路，x3---y2---x1----y3。取个反，冲突就解决了。x3 也找到了自己最满意的对象。
轮到 x4 了。x4 最满意的是 y2 和 y3，但是都被挑走了。我们先用匈牙利算法，给她也试一下。开始找增广路。x4----y2----x3----y3------x1----y2----????，发现到了 y2，找不下去了，又回到 y3 了。 我们优先广度，试试另一条路。 x4----y3-----x1------y2-----x3------y3----???，发现又找不下去了。
此时此刻，匈牙利算法也解决不了了，就要开始扩大择偶范围了。
第二步，最高标准调整。
我们随便选择一条上面没走下去的交替路（由于没有成功找到另一个未匹配的对象，所以这条交替路没有资格被称为增广路）比如就选这条：
x4----y2----x3----y3------x1----y2----????
现在我们看看，有哪些人和 x4 的失败有关。女生：x1，x3，x4。男生：y2，y3。
现在我们要协调这几个人的择偶最高标准（也就是他们的顶标），扩大择偶范围了。
首先，我们不能破坏原有的关系，原来的顶标都是设计好的，能保证选到自己最喜欢的对象。所以要保证他们之间最高标准不变，这样保证原来的匹配不会发生变化。
这里让上面和 x4 冲突的这些人里：女生的顶标减少，男生顶标增加，这样他俩合起来标准不变。
但是，女生的顶标减小了，其他人的机会就来了。
再回到刚刚我们挑子图的公式，就是小王配小李的这个等式： Swang +Sli =W，现在小王因为和别人冲突了，降低了标准，W 就减小了，也就是有些权重没那么大的边，现在有机会被加进子图里了。
现在女生：x1，x3，x4 都喜欢 y2 和 y3，发生冲突了，而 y1，y4，y5 还没被他们考虑。原本 x1 的标准是 5，现在她要考虑 y1 的话，x1y1 权重是 3，需要降低 2 个标准。
同理，x1y4 需要降低 1； x3y1 需要降低 2， x3y4 需要降低 4-1=3；x3y5 需要降低 4-0=4。x4 也一样算法。
所以考虑到最大权重，最少要降低 1 个标准。
因此我们把 x1，x3，x4 的标准 -1，y2，y3 对应 +1。
在这个标准下，我们依旧要挑满足“两人顶标和=两人连线权重”的边。
可以看出来，x4 同学降低标准后，所有男同学都满足她的标准了。
这时候按照匈牙利算法，x4 和 y1 配对，冲突了，找到增广路 x4---y1---x2---y4。取反后，x4 和 y1 配对，x2 和 y4 配对。
再给 x5 找对象。x5 也找到了 y5 作为对象。找到增广路径 x5---y4---x2---y1---x4---y5。取反后，x4 和 y1 配对，x2 和 y4 配对。
现在所有人都有对象了。此时他们的权重为 4+2+3+0+3+0+1+1 +0+0 =14。
4.4 定理&证明
如果二分图存在某组可行顶标，并且该可行顶标的相等子图存在完美匹配，那么该匹配就是原二分图的最佳匹配。
考虑原二分图的任意一组完美匹配 M ，其边权和 val(M) 等于每条匹配边（匹配边没有公共顶点）的权值和，又根据可行顶标的定义，我们可以得出任意一组完美匹配的边权和都小于等于任意一组可行顶标的点权和。
如果存在一组可行顶标且该可行顶标的相等子图存在完美匹配，那么该相等子图的完美匹配 M' 的边权和 val(M') 如下。（因为相等子图只存在 w(u, v) = l(u) + l(v) 的边）
显然对于任意的完美匹配 M，val(M) <= val(M')，所以 M'就是权值和最大的完美匹配，即最佳匹配。
4.5 代码实现
定义字段：
// 定义二分图，表示女生和男生之间的好感度，love[i][j] 存储了第 i 个女生对第 j 个男生的好感度
private int[][] love;
// 用于存储女生的顶标，顶标随着女生择偶标准的降低而调整
private int[] exGirl;
// 用于存储男生的顶标，顶标随着女生择偶标准的降低而调整
private int[] exBoy;
// 记录每轮匹配中哪些女生已经被尝试匹配
private boolean[] visGirl;
// 记录每轮匹配中哪些男生已经被尝试匹配
private boolean[] visBoy;
// 记录男生匹配到女生的索引 如果男生 i 匹配女生 j，则 match[i]=j。
private int[] match;
// 用于反映男生与妹子之间的期望值差距
private int[] slack;
为每个女生解决匹配问题（maxMatching）：
public int maxMatching() {
Arrays.fill(match, -1); // 初始化男生匹配状态 -1：未匹配
Arrays.fill(exBoy, 0); // 初始男生期望值为 0
// 初始化女生期望值，初始值是与她相连的男生中最大的好感度
for (int i = 0; i < N; ++i) {
exGirl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
exGirl[i] = Math.max(exGirl[i], love[i][j]);
}
}
for (int i = 0; i < N; ++i) {
Arrays.fill(slack, INF); // 初始化男生期望值为正无穷大，表示男生离被倾心还很远
while (true) {
// 用来标记哪些女生或者男生在 dfs 递归中被访问过
Arrays.fill(visGirl, false);
Arrays.fill(visBoy, false);
// 寻找增广路，找到则说明匹配成功，退出内层匹配继续匹配下一个女生
if (dfs(i)) {
break;
}
// 匹配失败...降低择偶标准...扩大择偶范围
int d = INF; // 找到最小可降低的期望值
for (int j = 0; j < N; ++j) {
if (!visBoy[j]) {
d = Math.min(d, slack[j]);
}
}
for (int j = 0; j < N; ++j) {
if (visGirl[j]) {
exGirl[j] -= d; // 降低女生期望值
}
if (visBoy[j]) {
exBoy[j] += d; // 男生顶标增加，男生和女生组合起来标准不变
} else {
slack[j] -= d; // 对未被访问过的男生，降低 slack 值，使得他们更接近被女生接受
}
}
}
}
int res = 0;
for (int i = 0; i < N; ++i) {
res += love[match[i]][i]; // 计算最大匹配值
}
return res;
}
实现寻找增广路的算法（DFS）：
private boolean dfs(int girl) {
visGirl[girl] = true; // 标记当前的女生被访问，避免重复匹配
for (int boy = 0; boy < N; ++boy) {
if (visBoy[boy]) {
continue; // 当前男生已经在本轮匹配中尝试过
}
// 计算当前男生和当前妹子的期望值差距
int gap = exGirl[girl] + exBoy[boy] - love[girl][boy];
if (gap == 0) { // 匹配成功
visBoy[boy] = true; // 标记当前的男生被访问
// 如果男生还未与任意女生匹配 || 能从男生出发匹配到增广路径
if (match[boy] == -1 || dfs(match[boy])) {
match[boy] = girl; // 能匹配到增广路径，将男生与女生进行匹配
return true;
}
} else {
// 更新女生和男生之间的期望值差距
slack[boy] = Math.min(slack[boy], gap);
}
}
return false;
}
完整代码实现：
package km;
import java.util.Arrays;
public class KuhnMunkres {
public static void main(String[] args) {
int[][] love = {
{3, 5, 5, 4, 1},
{2, 2, 0, 2, 2},
{2, 4, 4, 1, 0},
{0, 1, 1, 0, 0},
{1, 2, 1, 3, 3}
};
KuhnMunkres km = new KuhnMunkres(love);
int maxMatch = km.maxMatching();
System.out.println("最大匹配数：" + maxMatch);
System.out.println("匹配结果：");
for (int v = 0; v < love[0].length; v++) {
if (km.match[v] != -1) {
System.out.println("左边顶点 " + km.match[v] + " 匹配右边顶点 " + v);
}
}
}
private static final int INF = Integer.MAX_VALUE;
private int[][] love;
private int[] exGirl;
private int[] exBoy;
private boolean[] visGirl;
private boolean[] visBoy;
private int[] match;
private int[] slack;
private int N;
public KuhnMunkres(int[][] love) {
this.N = love.length;
this.love = love;
exGirl = new int[N];
exBoy = new int[N];
visGirl = new boolean[N];
visBoy = new boolean[N];
match = new int[N];
slack = new int[N];
}
public int maxMatching() {
Arrays.fill(match, -1);
Arrays.fill(exBoy, 0);
for (int i = 0; i < N; ++i) {
exGirl[i] = love[i][0];
for (int j = 1; j < N; ++j) {
exGirl[i] = Math.max(exGirl[i], love[i][j]);
}
}
for (int i = 0; i < N; ++i) {
Arrays.fill(slack, INF);
while (true) {
Arrays.fill(visGirl, false);
Arrays.fill(visBoy, false);
if (dfs(i)) {
break;
}
int d = INF;
for (int j = 0; j < N; ++j) {
if (!visBoy[j]) {
d = Math.min(d, slack[j]);
}
}
for (int j = 0; j < N; ++j) {
if (visGirl[j]) {
exGirl[j] -= d;
}
if (visBoy[j]) {
exBoy[j] += d;
} else {
slack[j] -= d;
}
}
}
}
int res = 0;
for (int i = 0; i < N; ++i) {
res += love[match[i]][i];
}
return res;
}
private boolean dfs(int girl) {
visGirl[girl] = true;
for (int boy = 0; boy < N; ++boy) {
if (visBoy[boy]) {
continue;
}
int gap = exGirl[girl] + exBoy[boy] - love[girl][boy];
if (gap == 0) {
visBoy[boy] = true;
if (match[boy] == -1 || dfs(match[boy])) {
match[boy] = girl;
return true;
}
} else {
slack[boy] = Math.min(slack[boy], gap);
}
}
return false;
}
}
输出结果：
最大匹配数：14
匹配结果：
左边顶点 1 匹配右边顶点 0
左边顶点 2 匹配右边顶点 1
左边顶点 0 匹配右边顶点 2
左边顶点 4 匹配右边顶点 3
左边顶点 3 匹配右边顶点 4
转载自:https://juejin.cn/post/7343753562516570148