算法笔记_138:稳定婚姻问题(Java)
16lz
2021-01-22
目录
1 问题描述
2 解决方案
1 问题描述
何为稳定婚姻问题?
有一个男士的集合Y = {m1,m2,m3...,mn}和一个女士的计划X = {n1,n2,n3,...,nn}。每一个男士有一个排序的列表,把女士按照潜在的优先级进行排序。同样,每一个女士也有一个男士的优先级列表。现在,把男士和女士进行配对,要求尽可能的符合优先级的要求。使得最终的配对结果,男士对女士都可接受,不会出现拒绝的情况,即每对男士和女士都是稳定的。
2 解决方案
上述对于稳定婚姻问题的解释有点牵强,具体可以看一下下面截图:
下面代码所使用的男士和女士集合数据是上图的实例,即男士3人,女士3人。
具体代码如下:
package com.liuzhen.practice;
import java.util.Scanner;
public class Main {
public void getResult(int[][] boys, int[][] girls) {
int[] result = new int[boys.length];
int[] used = new int[girls.length]; //最终女士配对的男士
for(int i = 0;i < girls.length;i++) {
used[i] = -1;
result[i] = -1;
}
int count = 0; //统计已完成配对个数
while(count < boys.length) {
for(int i = 0;i < boys.length;i++) {
if(result[i] != -1) //当男士i已完成配对时,进行下一个男士配对
continue;
for(int j = 0;j < boys[0].length;j++) {
if(used[boys[i][j]] == -1) {
used[boys[i][j]] = i; //女士boys[i][j]与男士i配对
result[i] = boys[i][j]; //男士i和女士boys[i][j]配对
break; //男士i完成配对,退出循环
} else {
int temp = 0, temp1 = 0;
for(;temp < girls[0].length;temp++) { //求出男士i在女士boys[i][j]心中的优先级
if(girls[boys[i][j]][temp] == i)
break;
}
for(;temp1 < girls[0].length;temp1++) { //求出当前女士已配对男士在其心中的优先级
if(girls[boys[i][j]][temp1] == used[boys[i][j]])
break;
}
if(temp < temp1) { //当男士i比目前已与女士配对的男士优先级要高时
result[used[boys[i][j]]] = -1; //已配对男士被踢
used[boys[i][j]] = i; //当前女士的配偶换成男士i
result[i] = boys[i][j];
break; //男士i完成配对,退出循环
}
}
}
}
count = 0;
for(int i = 0;i < used.length;i++) {
if(used[i] != -1)
count++;
}
}
//打印出结果
for(int i = 0;i < result.length;i++)
System.out.println("男士"+i+"和女士"+result[i]+"配对");
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] boys = new int[n][n]; //男士的心中对象优先级
int[][] girls = new int[n][n]; //女士的心中对象优先级
for(int i = 0;i < n;i++) {
int one = in.nextInt(); //优先级为1
int two = in.nextInt(); //优先级为2
int three = in.nextInt(); //优先级为3
boys[i][0] = one;
boys[i][1] = two;
boys[i][2] = three;
}
for(int i = 0;i < n;i++) {
int one = in.nextInt(); //优先级为1
int two = in.nextInt(); //优先级为2
int three = in.nextInt(); //优先级为3
girls[i][0] = one;
girls[i][1] = two;
girls[i][2] = three;
}
test.getResult(boys, girls);
}
}
更多相关文章
- 字体图标的引入和通过媒体查询改变导航样式
- HTML样式和常用选择器
- 字体图标的引用和自定义样式/媒体查询的使用
- 数据库的CURD操作、PDO本质与原理的学习
- CSS之伪类选择器和简单盒子简单案例
- 伪类选择器与盒模型常用属性
- 伪类选择器-结构伪类、根据位置选择匹配
- 7.4——常用标签与应用场景之表格与单元格
- css伪类选择器和盒模型