本文主要是介绍匈牙利算法学习笔记_Python代码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
学习华为上机测试题，遇见了下面题，很有意思，核心是匈牙利算法问题。
特此学习记录。资料均参考自网络。
匈牙利算法目的：找出两边最大的匹配的数量。
参考资料：
https://blog.csdn.net/u013377068/article/details/79893013
https://blog.csdn.net/sunny_hun/article/details/80627351
https://www.nowcoder.com/profile/8408989/codeBookDetail?submissionId=25842225
题目描述：
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。
输出:输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入说明：1 输入一个正偶数n， 2输入n个整数
输出描述: 求得的“最佳方案”组成“素数伴侣”的对数。
# In[]# 匈牙利算法
# 别人代码
def prime_judge(n): #判断一个数是否是素数m=int(n**0.5)if n%2==0:return Falseelse:for i in range(m+1)[3::2]:if n%i==0:return Falsereturn Truedef group_lst(lst): #判断列表内数为奇偶数，并分开存放a = []b = []for i in lst:if int(i)%2 == 1:a.append(int(i))else:b.append(int(i))return (a, b)def matrix_ab(a, b): #构建一个a行b列的二维矩阵，矩阵内容为1表示a+b为素数，为0表示a+b不是素数matrix = [[0 for i in range(len(b))] for i in range(len(a))]for ii, i in enumerate(a):for jj, j in enumerate(b):if prime_judge(i+j) == True:matrix[ii][jj] = 1return matrixdef find(x): #匈牙利算法匹配for index, i in enumerate(b):if matrix[x][index] == 1 and used[index] == 0: # 男女有好感 且 这个女的还没有和男的匹配过used[index] = 1if connect[index] == -1 or find(connect[index]) != 0: # 如果这个女的还单身 或者 这个女的已经配好的男的还能去找别的女的（递归）connect[index] = x # 匹配成功 第x号男的 和 第index号女的 return 1return 0while True: #理解a,b为男女配对的话try:n = int(input())m = input().split()(a, b) = group_lst(m)matrix = matrix_ab(a, b)connect = [-1 for i in range(len(b))] #标记这个女的是否已经配对成功count = 0 for i in range(len(a)): used = [0 for j in range(len(b))] # 女的是否被这个男的查找过了if find(i): #从当前男的开始查找count += 1 # 配对成功+1（这个男女的配对可能会变，但是数量不变）print(count)except:break
这篇关于匈牙利算法学习笔记_Python代码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
