素数伴侣——匈牙利算法

题目描述

若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:

输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。

数据范围：1 \le n \le 100，输入的数据大小满足 2 \le val \le 30000

输入描述：

1 输入一个正偶数 n
2 输入 n 个整数

输出描述：

求得的“最佳方案”组成“素数伴侣”的对数。

示例

输入：

4
2 5 6 13
2
3 6

输出：

2
0

首先容易想到的点：

• 要想和为素数，这两个数必定是一奇一偶，不能是同奇或同偶
• 组成素数最多的情况，不会超过min(奇数个数,偶数个数)。

求解过程

依据上面的想法，我有了两种解法，第一种是在当时做的时候想出来的，虽然能解答出来，但是我并不清楚算法是否完全正确，所以可以忽略；第二种是做完后参考了其他人的解法去实现的，也就是匈牙利算法。

在这题的正式解法中，一个必须的过程就是判断是否为素数，这个方法相信都比较熟悉了，很快能实现。

def isprime(x):  # 判断x是否为素数
    t = 2
    while t ** 2 <= x:  # 和枚举根号x是一样的
        if x % t == 0:
            return False
        else:
            t += 1
    return True

直接实现

了解到组成素数必须要为一奇一偶后，就可以把输入的数组 an分成奇偶两组，然后遍历两个数组，找出每个能组成素数的组合，最后进行配对，尽可能多的产生素数组合。这里可以不用先找素数再匹配，匈牙利算法中是在匹配的过程中判断素数的。这里重要的是匹配的过程，而我是在匹配之前完成了素数的判断。

n = int(input())  # 获取n
an = [int(x) for x in input().strip().split(' ')]  # 输入的n个整数
odd = [x for x in an if x % 2 != 0]  # 把输入的整数分成偶数和奇数
even = [x for x in an if x % 2 == 0]
# 要组成素数，两个数一定不能同为偶数或奇数，必须一奇一偶
if len(odd) > len(even):
    odd, even = even, odd
xn = []  # 存储素数组合
for i in range(len(odd)):
    yn = []  # 对应可以组成素数的序号
    for j in range(len(even)):
        if isprime(odd[i] + even[j]):  # 两层循环找出素数组合
            yn.append(j)  # j号元素可以和i位组成素数
    xn.append(yn)

上面这段代码的处理是生成了素数组合的嵌套列表 xn，xn的一维索引表示的是奇数组(偶数组)的序号，xn[i](yn)也为数组，xn[i][j](yn[j])表示的是第 i号奇数(偶数)与 j号偶数(奇数)可以组成素数。

那么关键来了，现在知道了哪几个数可以组成素数，那么怎么匹配他们让组成素数的组数最大？我思考后，想出了以下算法过程，但我并不能科学的证明这样求出来的是最大的组数，仅仅是凭感觉的认为它是最大的组数。

输入嵌套数组xn
初始化matched集合为空(记录已经匹配的序号)
while xn非空:
	生成cnt计数器(对所有yn计数)
    once <- yn中只出现过一次的元素(cnt = 1)
    if once为空:
        for xn:
            if xn[i]为空:
                弹出xn第i组yn
                break
            elif xn[i]长度最小:
                xn[i][0]添加到matched集合中
                删除xn中其它地方出现的xn[i][0]
                弹出xn第i组yn
                break
    else:
        for xn:
            if xn[i]为空:
                弹出xn第i组yn
            elif xn[i]存在元素sp∈once:
                把sp添加到matched集合中
                弹出xn第i组yn
            break

返回 matched的长度

流程图如下：

整体来说就是在匹配的过程中优先满足可选范围小的数，比如说有一个数只能和另一个数组成素数，那么应该优先满足它，对于其他数还有其他选择。这样不断从 xn中剔除只有一个匹配项的数和空集，不断更新计数器，当所有数都有多个选择时，也是优先从长度更小的 yn中选择，然后继续循环更新、弹出，最后直至 xn为空，matched集合的长度就是最大组合数了。

我觉得还是太复杂了，兴许就只能看看，重点还是下面的匈牙利算法理解起来简单。

匈牙利算法

了解匈牙利算法，可以到网上搜索下，知乎上有个匈牙利算法 可以看看。

类似的将数组分奇偶两组后，循环其中一个数组(哪个都行)，进行匹配，匹配成功 group_num数值就会加1。

n = int(input())  # 获取n
an = [int(x) for x in input().strip().split(' ')]  # 输入的n个整数
odds = [x for x in an if x % 2 != 0]  # 把输入的整数分成偶数和奇数
evens = [x for x in an if x % 2 == 0]
m = len(odds)
k = len(evens)
group_num = 0  # 最终匹配的组数
matched = [0] * k  # 存储数组中每个数是否被匹配，匹配成功则存储对应的值，否则为0
for od in odds:  # 循环另一个数组
    vis = [0] * n  # 保存这一轮循环中数组中的数是否被访问，没有访问过才会进行下一步操作
    if match(od, evens, matched):  # 判断od这个数在evens中匹配哪一个，能匹配则group_num加1
        group_num += 1
print(group_num)

同样总结下算法的流程：

match(要匹配的数od, 数组evens, 记录是否匹配的数组matched)
for i in range(len(evens)):
    if (od + evens[i]是素数) 并且 evens[i]没有被访问过(即vis[i] == 0)
        把evens[i]设为已访问(即vis[i] = 1)
        if evens[i]还没有被匹配(即matched[i] == 0) 或者 match(matched[i], evens, match):
            第i个数evens[i]与数od匹配matched[i] = od
            返回 True
返回 False

下面举个简单的例子画图来理解里面 match函数的递归作用