山东诚铭建设机械有限公司网站,站内内容投放计划,wordpress 会员系统,企业网站代码模板下载剪枝
将搜索过程中一些不必要的部分剔除掉#xff0c;因为搜索过程构成了一棵树#xff0c;剔除不必要的部分#xff0c;就像是在树上将树枝剪掉#xff0c;故名剪枝。
剪枝是回溯法中的一种重要优化手段#xff0c;方法往往先写一个暴力搜索#xff0c;然后找到某些特…剪枝
将搜索过程中一些不必要的部分剔除掉因为搜索过程构成了一棵树剔除不必要的部分就像是在树上将树枝剪掉故名剪枝。
剪枝是回溯法中的一种重要优化手段方法往往先写一个暴力搜索然后找到某些特殊的数学关系或者逻辑关系通过它们的约束让搜索树尽可能浅而小从而达到降低时间复杂度的目的。
一般来说剪枝的复杂度难以计算。
例题
蓝桥oj2942数字王国之军训排队
问题描述
数字王国开学了它们也和我们人类一样有开学前的军训现在一共有 n 名学生每个学生有自己的一个名字 ai数字王国里的名字就是一个正整数注意学生们可能出现重名的情况此时叛逆教官来看了之后感觉十分别扭决定将学生重新分队。
排队规则为将学生分成若干队每队里面至少一个学生且每队里面学生的名字不能出现倍数关系注意名字相同也算是倍数关系。
现在请你帮忙算算最少可以分成几队
例有 4 名学生 (2,3,4,4)最少可以分成 (2,3)、(4)、(4) 共 3 队。
输入格式
第一行包含一个正整数 n表示学生数量。
第二行包含 n 个由空格隔开的整数第 i 个整数表示第 i 个学生的名字 ai。
输出格式
输出共 1 行包含一个整数表示最少可以分成几队。
样例输入
4
2 3 4 4样例输出
3解1.不剪枝
#include iostream
#includevector
#includealgorithm
using namespace std;
const int N 15;
int a[N],n;vectorintv[N];//v[i]表示第i组里面所有人的编号//cnt表示队伍数量dfs返回在cnt个队伍的情况下是否可以成功分组bool dfs(int cnt, int dep)
{if (dep n 1){//说明每个人都成功分组了//检查当前方案的合法性for (int i 1; i cnt; i)//每个队伍枚举里面所有的二元组{for (int j 0; j v[i].size(); j){for (int k j1; k v[i].size(); k){if (v[i][k] % v[i][j] 0)return false;}}}return true;}//枚举每个人所属的队伍for (int i 1; i cnt; i){v[i].push_back(a[dep]);if (dfs(cnt, dep 1))return true;//恢复现场v[i].pop_back();}return false;
}int main()
{// 请在此输入您的代码cin n;for (int i 1; i n; i)cin a[i];sort(a 1, a 1 n);//枚举n个for (int i 1; i n; i){if (dfs(i, 1))//i个队伍从第一层开始搜索看这种情况是否可以装的下即成功分组{cout i endl;break;}}return 0;
}
解2.剪枝我没太懂先放着
#include iostream
#includevector
#includealgorithm
using namespace std;
const int N 15;
int a[N],n;vectorintv[N];//v[i]表示第i组里面所有人的编号//cnt表示队伍数量dfs返回在cnt个队伍的情况下是否可以成功分组bool dfs(int cnt, int dep)
{if (dep n 1){//说明每个人都成功分组了//检查当前方案的合法性for (int i 1; i cnt; i)//每个队伍枚举里面所有的二元组{for (int j 0; j v[i].size(); j){for (int k j1; k v[i].size(); k){if (v[i][k] % v[i][j] 0)return false;}}}return true;}//枚举每个人所属的队伍for (int i 1; i cnt; i){bool tag true;
for(const auto j:v[i])if (a[dep] % j 0){tag false;break;}
if (!tag)continue;v[i].push_back(a[dep]);if (dfs(cnt, dep 1))return true;//恢复现场v[i].pop_back();}return false;
}int main()
{// 请在此输入您的代码cin n;for (int i 1; i n; i)cin a[i];sort(a 1, a 1 n);//枚举n个for (int i 1; i n; i){if (dfs(i, 1))//i个队伍从第一层开始搜索看这种情况是否可以装的下即成功分组{cout i endl;break;}}return 0;
}
