算法分析

dfs

依次遍历所有的数，通过第u个数往现有的k集合中放，遍历所有情况

• 第u个数往第1个集合放

• 第u个数往第2个集合放

• …

• 第u个数往第k个集合放

• 新开一个集合，第u个数往第k + 1个集合中放

参考文献

算法提高课

Java 代码

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N = 11;
    static int n;
    static int[] a = new int[N];
    static boolean[] st = new boolean[N];
    static ArrayList[] g = new ArrayList[N];
    static int res = 0x3f3f3f3f;
    static int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    //检查x数能否在t集合中存活
    static boolean check(int x, ArrayList<Integer> t)
    {
        int len = t.size();
        for(int i = 0;i < len;i ++)
        {
            if(gcd(x , t.get(i)) > 1) return false;
        }
        return true;
    }
    //放第u个数，共有k个组
    static void dfs(int u, int k)
    {
        if(u == n)
        {
            res = Math.min(res, k);
            return ;
        }
        for(int i = 0;i < k;i ++)
        {   //若能在第i个集合中放，则尝试放
            if(check(a[u], g[i]))
            {
                g[i].add(a[u]);
                dfs(u + 1, k);
                g[i].remove(g[i].size() - 1);
            }
        }
        //新开一个组

        g[k].add(a[u]);
        dfs(u + 1, k + 1);
        g[k].remove(g[k].size() - 1);
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 0;i < n;i ++)
        {
            a[i] = scan.nextInt();
        }
        for(int i = 0;i <= 10;i ++) g[i] = new ArrayList<Integer>();
        dfs(0, 0);
        System.out.println(res);
    }
}