网站开发工程师适合女生吗,黑龙江省城乡和住房建设厅网站首页,源码管理 网站,做印尼购物网站如何发货目录 1 介绍2 训练 1 介绍
本专题用来记录使用dfs剪枝技巧求解的题目。
剪枝有以下思路#xff1a;
优化搜索顺序。可行性剪枝。最优性剪枝。唯一性剪枝#xff0c;也叫去除冗余。记忆化搜索#xff0c;也叫dp。
2 训练
题目1#xff1a;165小猫爬山
C代码如下#… 目录 1 介绍2 训练 1 介绍
本专题用来记录使用dfs剪枝技巧求解的题目。
剪枝有以下思路
优化搜索顺序。可行性剪枝。最优性剪枝。唯一性剪枝也叫去除冗余。记忆化搜索也叫dp。
2 训练
题目1165小猫爬山
C代码如下
#include iostream
#include cstring
#include algorithm
#include vectorusing namespace std;const int N 20;
int n, m;
vectorint a;
vectorvectorint group;
int res 20;bool check(int x, int j) {int s 0;for (auto v : group[j]) s v;return s x m;
}void dfs(int i, int groupsize) {if (groupsize res) {//最优性剪枝return;}if (i n) {res groupsize;}int x a[i];//将x放入哪个组for (int j 0; j groupsize; j) {//将x放入第j组if (check(x, j)) { //可行性剪枝group[j].emplace_back(x);dfs(i 1, groupsize);group[j].pop_back();}}//新开一个组group[groupsize].emplace_back(x);dfs(i 1, groupsize 1);group[groupsize].pop_back();return;
}int main() {cin n m;a.resize(n 1);for (int i 0; i n; i) cin a[i];group.resize(n 1);sort(a.begin(), a.end());reverse(a.begin(), a.end()); //从大到小枚举优化搜索顺序//放置原则dfs(0, 0);cout res endl;return 0;
}题目2
