分成互质组

原题链接
给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

输入格式
第一行是一个正整数 n。

第二行是 n 个不大于10000的正整数。

输出格式
一个正整数，即最少需要的组数。

数据范围
1≤n≤10
输入样例：
6
14 20 33 117 143 175
输出样例：
3

依次枚举每一组的情况，如果当前组能装下当前枚举的数就将当前数加入到当前组
如果当前组没有不能容下当前枚举的数，就新开一组
当已被加入组中的数和输入的数相同是，更新答案

#include<iostream>
#include<string>
using namespace std;

const int N = 15;

int n,a[N];
int g[N][N],ans = N; 
bool st[N];

int gcd(int a,int b)//求最小公约数
{
	return b ? gcd(b,a%b) : a;
}

bool check(int cnt,int gc,int i) //检查能不能将当前枚举的数a[i]，装入当前组g[cnt]中
{
	if(!gc)	return true;
	for(int j = 0; j < gc; j++)
		if(gcd(g[cnt][j],a[i]) > 1)	return false;
	return true;
}

void dfs(int cnt,int gc,int tc,int start)
{//cnt 当前枚举的组数；gc 当前组中的元素个数；tc 已装入组中的元素个数；start 当前枚举的数的下标，不设这个会TLE
	if(tc == n)
	{
		ans = min(cnt,ans); // 更新答案
		return;
	}
	
	bool flag = true;
	for(int i = start; i <= n; i++)
	{
		if(!st[i] && check(cnt,gc,i))
		{
			g[cnt][gc] = a[i];
			st[i] = true;
			flag = false;//当前组能装元素
			
			dfs(cnt,gc + 1,tc + 1,i + 1); // 尝试往当前组g[cnt]中装新元素			
			g[cnt][gc] = 0;
			st[i] = false;//当前元素从g[cnt]中取出
		}
	}
	
	if(flag)	dfs(cnt + 1,0,tc,1);//枚举的数都装不进g[cnt]，新开一组，g[cnt + 1]
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)	cin >> a[i];
	
	dfs(1,0,0,1);
	
	cout << ans << endl;
	
	return 0;
} 

本文地址：https://blog.csdn.net/yulong_D/article/details/107882412