匈牙利算法

匈牙利算法思想：先到先得，能让则让。

1.例题

输入:
    有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
​
已知条件：
    1.“素数伴侣”:两个自然数相加之和为质数
    2.每个待挑选的自然数只能选择一次进行组合
​
输出:
    输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
​
示例：
    输入：
        4
        2 5 6 13
        2
        3 6
​
    输出：
        2
        0

2.算法程序

class Solution{
    private ArrayList list1; //存放奇数
    private ArrayList list2; //存放偶数
    private boolean [] visit; //数字是否被访问
    private int [] match;    //存放当前元素所匹配的数字
    private int counter;    //计数
    public Solution(){}
    public Solution(int[] nums){
        classify(nums); //分类奇数和偶数
        traverse();
    }
    
    //******按照奇数偶数分类*********
    private void classify (int[] nums){
        //1.声明存放列表
        list1 = new ArrayList<>();
        list2 = new ArrayList<>();
        //2.按照奇数偶数分类
        for(int i : nums){
            if((i&1)==1) {
                list1.add(i);
            }
            else{
                list2.add(i);
            }
        }
        //3.建立list2所匹配的元素标识
        visit = new boolean [list2.size()];//是否被访问
        match = new int[list2.size()];     //是否有匹配
        Arrays.fill(match,-1);             //初始无匹配
    }
//*********************************************************
    //遍历Array1
    private void traverse(){
        counter =0;
        for(int i=0;i 
3.调用程序 
import java.util.*;
​
public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        //判断是否还有输入
        while(scan.hasNext()){
            int n = scan.nextInt();
            int[] nums = new int[n];
            for(int i=0;i
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/langs/1353812.html