枚举每一组可以放哪些元素。
代码及巨无霸详解注释
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
int n;
int a[N];//n个整数
int ans = N;//由于是求最小值，这里初始化为最大值
int g[N][N];//分组
int st[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
bool check(int g[],int x,int start){
for(int i=0;i<start;i++){
if(gcd(g[i],x)>1) return false;
}
return true;
}
//当前要放在哪个分组；要放在该分组的第几个位置；从哪个位置开始选择元素【组合套路(定一个遍历顺序)】；当前已分组完毕的元素个数
void dfs(int gr,int gc,int start,int cnt){
if(gr>=ans) return;//剪枝 + 防止死循环
if(cnt==n) ans=gr;
bool flag=true;//从start开始找，是否有元素不能放到gr组中
for(int i=start;i<n;i++){
if(!st[i]&&check(g[gr],a[i],gc)){
st[i]=true;
g[gr][gc]=a[i];
dfs(gr,gc+1,i+1,cnt+1);
st[i]=false;
flag=false;
}
}
//新开一个分组
//由于dfs每层之间确定了顺序，所以期间是会有元素被漏掉的，【比如一开始你找的一串序列(1)是1,2,3,4 但是第二次(2)是1,3,4 很显然此时
//(2)还有一个3没有得到分组，需要从start=0开始再把它找出来！ 因此这样做仿佛有点浪费时间呢！！】
//因此当所有元素都不能放进当前分组的时候 或者 当start=n-1了但是元素没有全部分组完毕时，要重新从start=0开始找，并且一定要有st数组！！！不然会把一个元素重复的分组！
if(flag) dfs(gr+1,0,0,cnt);
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
//为什么一开始gr从1开始但是分组只开了10个呢？
//首先这样的话可以直接通过gr就得到当前分了多少组；其次由于ans初始化即为10，因此当打算开第10个分组时，会被弹回，数组不会越界
dfs(1,0,0,0);
cout<<ans;
return 0;
}
枚举每个元素可以放在哪一组
代码及注释
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=10;
int a[N];
vector<int> g[N];
int n;
int ans=10;
int len=0;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
bool check(int c,int x){
for(int i=0;i<g[c].size();i++){
if(gcd(g[c][i],x)>1) return false;
}
return true;
}
void dfs(int u){
if(u==n){
ans=min(ans,len);
return;
}
//每个元素的方法即——放到当前已经存在的组中 或者 放到新开的组中
for(int i=0;i<len;i++){
if(check(i,a[u])){
g[i].push_back(a[u]);
dfs(u+1);
g[i].pop_back();
}
}
//可见这里的len代表着的是当前开辟数组的个数
g[len++].push_back(a[u]);
dfs(u+1);
g[--len].pop_back();
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
dfs(0);
cout<<ans;
return 0;
}
对于以上的两种搜索的顺序其实可以想象一下这样的一种情景。即你有n个篮子你要用它们去装水果，每个篮子只能装对应种类的水果。
那么第一种方法就相当于是，你把水果任意的排成一排，然后拿着一个篮子从第一个水果开始一个个的往后看，看看能能放到你的这个篮子中。
对于第二种方法相当于是，你把篮子放一排，你拿着水果，然后一个个的往下看，看看能不能放在篮子里。
tql
第一个方法y总分析了那么多优化没想到是第二个快，哈哈哈哈，无情！必须支持！
可以把这句
dfs(gr,gc+1,start+1,cnt+1);改成dfs(gr,gc+1,i+1,cnt+1);实测耗时减半。。谢谢~已经修改
想知道二维数组为什么可以只把自己的一维当作参数传出去？求解orz
知道了就好
因为数组的本质是指针
感谢
第一种方法里面
这句为啥不能写成
我去下一个组搜索的时候为啥不能直接从start开始而是要从0开始呢
插眼，同问
考虑2, 4, 5, 8, 16
首先将2加入分组1，在for循环中，会将5加入分组，加下来进入递归判断8
从8开始的后面所有元素都无法放入分组1，因此需要开一个新的分组
此时start为3, 而4, 也就是下标为1的元素仍然未放入分组，如果参数填start的话会漏掉4
这个元素, 所以这里的参数需要填0
不错不错，最喜欢看这种yxc原版语录
那位大佬能够科学解释一下，既然当前数组可以放下，就不用新开，那么为什么不直接用贪心
可以用贪心，甚至可以用并查集都扫一遍，
搞错了， 不能用贪心， 把y总的源码中复原现场的做法删掉就是贪心的做法，贪心的做法不一定对，你把复原现场的st[i] = false删掉之后教一下，发现第一个数据就被卡了， 本来只用分成两组的，贪心的做法分出来的是三组。
这里的爆搜是把所有能贪心分组的情况通过复原现场都爆搜出来了、
因为你并不知道把这个数放到当前数组中会对后续放入产生什么影响。
这里有组同样的数据数据：
用这种贪心分组法的话，会分成
但是这里换下顺序：
会分成
答案是错的，而且显然贪心不能因为顺序改变就改变答案
如果按大佬和y总的方式，显然是枚举，只是剪掉了一些不好的答案
不是这样的，贪心不是这个意思，贪心是如果可以放入已经有的任何一组，那么不开新组
这样按你的那个数据算出来结果仍是2，但是有一个新的数据 不满足 3 7 6 14，这样贪心的错误在于
错误思路是如果当前这个数可以放入一个原本的却又开了新的，那这个数放原本也可，由此错误的以为可以贪心，但是并不是放原本的也可,因为原本的在后来又加入了新的数这样一来就不一定满足了
啥意思呀？
我这说的贪心就是能放入已有组，就不新开呀
你看这里的第二种顺序：
第一个数3，新开一组
第二个数6，不能放在已有的一组，新开一组
第三个数5，能放在第一组
第四个数10，不能放在已有组中，新开一组
就是说先后顺序会影响答案，得出不同的答案，那么就是不能用贪心的
5可以放已有第二组
3 10
6 5
你这样是只能放在已有的第一组了
想请教下第一种解法里需要新开一个组的情况下关于start需要从0开始的注释，这段里的 “比如一开始你找的一串序列(1)是1,2,3,4 但是第二次(2)是1,3,4 很显然此时(2)还有一个3没有得到分组”不太理解。(1)和(2)加小括号是啥意思？另外1，2是在枚举谁？谢谢！
想请教下第一种解法里需要新开一个组的情况下关于start需要从0开始的注释，这段里的 “比如一开始你找的一串序列(1)是1,2,3,4 但是第二次(2)是1,3,4 很显然此时(2)还有一个3没有得到分组”不太理解。(1)和(2)加小括号是啥意思？另外1，2是在枚举谁？谢谢！
请问一下第一个方法如何证明能枚举到所有情况呢（还是有点理解不了把水果排成一排用篮子装这种思路。。。
上面水果和篮子是对枚举顺序的说明，方便记忆。。针对这一题来说的话，第一个方法并没有枚举所有的情况，对搜索做了一定的优化。我们的策略是假如当前水果能放的话就放进去，不能放的话就再新开一个数组放。
因为：假如当前质数a能够放到x组，但你选择放在y组的话，那么最终得到了最优解时，你把a组从y组拿到x组，其实没有影响，因为y组里没有a之后组内依然互质，由于本来就可以放到x组，所以x组放了a之后也是互质的。
我好像理解了，谢谢你的帮助
请问为什么这个
if(gr>=ans) return;//剪枝 + 防止死循环可以防止死循环，我自己模仿写了一个，超时了，T…T加了一个start就过了，不过不了解，为什么会出现死循环呢，我在自己电脑上跑能跑出结果，谢谢。
if(gr>=ans) return;//剪枝 + 防止死循环是因为，这里最多只会开ans个组，当gr达到ans之后就会return不会再递归了不加start的话相当于是在搜一颗排列树，那样个结点都会往下有n个结点，树非常的庞大；我想组合数和排列树搜索的结点区别就和数学上全排列A和组合C的区别差不多吧。所以当树的结点变多的时候可能会超时。
并且上面的第一种写法和第二种写法相比时间已经很极限了，具体可以看运行时间，由于搜索顺序的不同运行时间差异挺大的
好的，谢谢