贪心和深搜(题目:素数伴侣)
中心思想:将所有数分为奇数和偶数,分别找到每一个奇数(偶数)的素数伴侣,可能有多个,都记录下来。先匹配伴侣少的奇数(偶数),再匹配伴侣多的奇数(偶数),这样就会找到尽可能多的素数伴侣对,组成素数伴侣的对数最多就是奇数(偶数)的个数(取决于奇数和偶数谁个数少)
步骤及示例:
#1.将所有数分为偶数even(ArrayList)和奇数odd(ArrayList),分别从小到大排序(假设长度较小的为odd)
#2.开辟一个长度和odd相同的list数组,list[i]存储:odd[i]的素数伴侣even[j]的所有j值
#3.将list按照元素个数的多少从小到大排序(并且去掉奇数没有素数伴侣的项)
---------------------------例子-----------------------------
22
20923 22855 2817 1447 29277 19736 20227 22422 24712 27054 27050 18272 5477 27174 13880 15730 7982 11464 27483 19563 5998 16163
---------------------------例子-----------------------------
even:5998 7982 11464 13880 15730 18272 19736 22422 24712 27050 27054 27174
odd:1447 2817 5477 16163 19563 20227 20923 22855 27483 29277
odd的素数伴侣:
1447:11464,22422,27174----下标为:2,7,11
2817:7982,11464,18272,24712,27050----下标为:1,2,5,8,9
5477:27054----下标为:10
16163:19736----下标为:6
19563:5998----下标为:0
20227:22422 24712----下标为:7,8
20923:5998 15730 27054----下标为:0,4,10
22855:11464----下标为:2
27483:没有
29277:15730----下标为:4
组成的list数组如下,并将list按照元素个数从小到大排序:
0: 10
1: 6
2: 0
3: 2
4: 4
5: 7,8
6: 2,7,11
7: 0,4,10
8: 1,2,5,8,9
#4.开辟一个flag数组,大小和even相同,flag[i]用来标记even[i]是否已经参与匹配,然后如图从上往下进行匹配,即深度优先搜索,红色代表匹配成功,蓝色代表尝试匹配,匹配失败,采用一个变量maxNum用来记录可以匹配的最大个数。
特别需要注意的是:当搜索到list的第7项(下标7)时,由于even数组中的下标为0,4,10的偶数已经参与过匹配,所以在这一层没有匹配到的时候,应该跳到下一层继续匹配,只要当前匹配的层数没有超过list数组的长度。跳到下一层继续匹配体现在代码中如下图所示的if判断:
代码如下:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; public class Main { private static int maxNum = 0; private static boolean isFind = false; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = null; while((str = br.readLine()) != null) { isFind = false; maxNum = 0; ArrayList<Integer> even = new ArrayList<>(); ArrayList<Integer> odd = new ArrayList<>(); int num = Integer.valueOf(str); String strs[] = br.readLine().split(" "); for(int i = 0; i<strs.length; i++) { int temp = Integer.valueOf(strs[i]); if(temp % 2 == 0) even.add(temp); else odd.add(temp); } Collections.sort(even); Collections.sort(odd); if(even.size()==0 || odd.size() == 0) System.out.println(0); else { if(odd.size()>=even.size()) { buildList(even, odd); } else { buildList(odd, even); } } } } public static void dfs(ArrayList<Integer> list[], boolean flag[], int pos, int cnt) { if(isFind == true) return; if(cnt>maxNum) { maxNum = cnt; } if(maxNum == list.length) { isFind = true; return; } if(pos>=list.length) { return; } boolean isJug = true; for(int i = 0; i<list[pos].size() && isFind==false; i++) { if(flag[list[pos].get(i)] == false) { isJug = false; flag[list[pos].get(i)] = true; dfs(list, flag, pos+1, cnt+1); flag[list[pos].get(i)] = false; } } if (isJug == true && pos<list.length) { dfs(list, flag, pos+1, cnt); } } public static void buildList(ArrayList<Integer> min, ArrayList<Integer> max) { ArrayList<ArrayList<Integer>> arrList = new ArrayList<>(); for(int i = 0;i<min.size(); i++) { ArrayList<Integer> subList = new ArrayList<>(); for(int j = 0; j<max.size(); j++) { if(isPrime(min.get(i)+max.get(j)) == true) { subList.add(j); } } if(subList.size()>0) arrList.add(subList); } Object obj[] = arrList.toArray(); ArrayList<Integer> list[] = new ArrayList[obj.length]; for(int i = 0; i<obj.length; i++) { list[i] = (ArrayList<Integer>) obj[i]; } Arrays.sort(list, new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) { return o1.size()-o2.size(); } }); boolean flag[] = new boolean[max.size()]; if(list.length>0) { dfs(list, flag, 0, 0); System.out.println(maxNum); } else System.out.println(0); } public static boolean isPrime(int num) { if(num == 2) return true; if(num%2 == 0) return false; for(int i = 3; i<=(int)Math.sqrt(num)+1; i+=2) { if(num % i == 0) return false; } return true; } }