庆阳市建设局网站,门户网站开发公司排名,团购网站建设案例,网站建设和管理培训算法提高课笔记 目录 小猫爬山题意思路代码 数独题意思路代码 木棒题意思路代码 生日蛋糕题意思路代码 剪枝是什么意思呢#xff1f; 我们知道#xff0c;不管是内部搜索还是外部搜索#xff0c;都可以形成一棵搜索树#xff0c;如果将搜索树全部遍历一遍#xff0c;效率…算法提高课笔记 目录 小猫爬山题意思路代码 数独题意思路代码 木棒题意思路代码 生日蛋糕题意思路代码 剪枝是什么意思呢 我们知道不管是内部搜索还是外部搜索都可以形成一棵搜索树如果将搜索树全部遍历一遍效率会很低但如果我们能在搜索的过程中提前预知判断某一些不可能是正确答案的情况就可以不用遍历其下的子树从而提高我们的算法效率
我们可以从以下几个角度考虑剪枝
优化搜索顺序 优先选择分支较少的结点排除等效冗余 尽量保证不搜索重复的状态就是在不考虑顺序时采用组合的方式搜索可行性剪枝 不合法提前退出最优性剪枝 如果当前答案无论如何都比目前的最优解要差那就可以不要往下搜了记忆化搜索DP
接下来将通过例题来讲解
小猫爬山
原题链接
翰翰和达达饲养了 N 只小猫这天小猫们要去爬山。
经历了千辛万苦小猫们终于爬上了山顶但是疲倦的它们再也不想徒步走下山了呜咕_。
翰翰和达达只好花钱让它们坐索道下山。
索道上的缆车最大承重量为 W而 N 只小猫的重量分别是 C1、C2……CN。
当然每辆缆车上的小猫的重量之和不能超过 W。
每租用一辆缆车翰翰和达达就要付 1 美元所以他们想知道最少需要付多少美元才能把这 N 只小猫都运送下山
输入格式
第 1 行包含两个用空格隔开的整数N 和 W。
第 2…N1 行每行一个整数其中第 i1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数表示最少需要多少美元也就是最少需要多少辆缆车。
数据范围
1 ≤ N ≤ 18, 1 ≤ Ci ≤ W ≤ 108
输入样例
5 1996
1
2
1994
12
29输出样例
2题意
给出小猫重量、缆车承重问最少要多少缆车能把所有小猫运走
思路
枚举每只小猫有两种状态
放到当前这辆车上新开一辆车
优化
优化搜索顺序比较一只比较轻的猫和另一只比较重的猫显然是比较重的猫带来的分支数量较少因为如果猫非常重可以直接把车占满但是猫很轻的话我们就要考虑还要加什么别的猫因此将所有猫按从大到小排序优先放重猫可行性剪枝当发现目前小猫的重量已经超过缆车承重就不要再往下搜了最优性剪枝当发现目前缆车数量已经大于等于当前计算出的缆车最少数量就不要再搜索了
代码
#include bits/stdc.husing namespace std;const int N 20;int n, m;
int w[N];
int sum[N];
int ans N; // 最坏的情况:每只小猫占一辆车void dfs(int u, int k) // u:当前在搜第几只猫 k:当前在搜第几辆车
{// 最优性剪枝if (k ans) return;if (u n){ans k;return;}for (int i 0; i k; i ) // 遍历每一辆车// 可行性剪枝if (sum[i] w[u] m) // 称重符合条件{sum[i] w[u];dfs(u 1, k);sum[i] - w[u]; // 恢复现场}// 新开一辆车sum[k] w[u];dfs(u 1, k 1);sum[k] 0; // 恢复现场
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n m;for (int i 0; i n; i ) cin w[i];// 优化搜索顺序sort(w, w n);reverse(w, w n);dfs(0, 0);cout ans \n;
}数独
原题链接
数独是一种传统益智游戏你需要把一个 9×9 的数独补充完整使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行包含 81 个字符代表数独的 81 个格内数据顺序总体由上到下同行由左到右。
每个字符都是一个数字1−9或一个 .表示尚未填充。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行表示输入结束。
输出格式
每个测试用例输出一行数据代表填充完全后的数独。
输入样例
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end输出样例
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936题意
填好数独保证每行每列、每个3x3方块都包含1-9
思路
先做一个小优化看比如说一个3x3小方格中有哪些数字没被用过随意选择一个格子然后对这些数字依次枚举搜索即可
优化
优化搜索顺序选择格子时尽量选择分支数量较少的格子比如说一个格子有2种填法另一个格子有5种那肯定优先选择2种的可行性剪枝一旦与行列九宫格重复时就不要继续搜了位运算优化 特殊优化可以用一个九位的二进制数表示每一行数使用的状态 比如0 1 0 0 1 1 1 0 0 可以用来表示2 5 6 7还没用其他数字用过了 我们考虑这一位上能不能填这个数时应该考虑二进制数的交集即在行、列、九宫格的二进制数列上这个数字都为1表示在行、列、九宫格内这个数字都没有被使用我们才能用这个数直接按位与 这里有个比循环九次更好的办法——lowbit lowbit运算可以帮助我们在O(1)的时间复杂度内返回当前数里的最后一个1因此用lowbit循环就可以抠出来所有的1
好难啊好难啊qaq看代码注释吧还是
代码
#include bits/stdc.husing namespace std;const int N 9, M 1 N;int ones[M]; // 每个二进制数里1的个数
int mapp[M]; // 把二进制数换成第几位是1
int row[N], col[N], cell[3][3];
char str[100];void init() // 初始化将所有位置都标记成没用过(也就是标记成1)
{for (int i 0; i N; i ) row[i] col[i] (1 N) - 1;for (int i 0; i 3; i )for (int j 0; j 3; j )cell[i][j] (1 N) - 1;
}void draw(int x, int y, int t, bool is_set) // 在(x,y)这个位置填上/删去t 填上的话is_set为true 删去为false
{if (is_set) str[x * N y] 1 t; // t属于0-8 要把它换算成1-9else str[x * N y] .;int v 1 t; // t换算到在每一行的位置if (!is_set) v -v; // 若为清空操作则取反row[x] - v;col[y] - v;cell[x / 3][y / 3] - v;
}int lowbit(int x) // 返回二进制数的最后一个1以及这个1之后的所有0
{return x -x;
}int get(int x, int y) // 返回(x,y)能填的数字(二进制序列)
{return row[x] col[y] cell[x / 3][y / 3];
}bool dfs(int cnt)
{if (!cnt) return true; // 全部填完int minv 10; // 首先找分支数最少的空格将最少的分支数赋给maxxint x, y;for (int i 0; i N; i )for (int j 0; j N; j )if (str[i * N j] .) // 格子为空可以填数字{int state get(i, j); // 该格子能填的数字的交集if (ones[state] minv){minv ones[state]; // 更新最少分支数x i, y j; // xy存的就是分支数量最少的格子的坐标}}int state get(x, y);for (int i state; i; i - lowbit(i)){int t mapp[lowbit(i)]; // 得到最后一个1所在的位置draw(x, y, t, true); // 把t填进去if (dfs(cnt - 1)) return true; // 成功直接返回truedraw(x, y, t, false); // 失败就把填进去的值再删掉}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);// 打表得到ones和mappfor (int i 0; i N; i ) mapp[1 i] i; // 将所有2^k转化成k(也就是返回二进制数里唯一一个1的位置)for (int i 0; i 1 N; i )for (int j 0; j N; j )ones[i] i j 1; // 记下每个二进制数里1的个数while (cin str, str[0] ! e){init();int cnt 0; // 有多少位置没填for (int i 0, k 0; i N; i )for (int j 0; j N; j , k )if (str[k] ! .) // 位置不空就把值填进去{int t str[k] - 1;draw(i, j, t, true);}else cnt ; // 位置空就累加空位的数量dfs(cnt);puts(str);}
}木棒
原题链接
乔治拿来一组等长的木棒将它们随机地砍断使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据每组数据包括两行。
第一行是一个不超过 64 的整数表示砍断之后共有多少节木棍。
第二行是截断以后所得到的各节木棍的长度。
在最后一组数据之后是一个零。
输出格式
为每组数据分别输出原始木棒的可能最小长度每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于 50。
输入样例
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0输出样例
6
5题意
给出一些数将其分成若干组使每一组总和相等问最小的总和是多少
思路
木棒每一组的总和 木棍题目中输入的数据
先从小到大枚举木棒的长度length看木棍能不能组成该长度的木棒
优化
所有木棍的总长度sum必须能整除木棒的长度length才可能有解不能整除的情况直接回溯不要搜了优化搜索顺序先枚举比较长的木棍使之后的分支较少排除等效冗余 (1) 如果一根木棒里有第一根第二根两根木棍那么先用第一根和先用第二根达成的效果都是一样的因此按照组合数方式枚举 (2) 如果当前木棍加到当前木棒中失败那直接略过后面所有等长木棍 (3) 如果是木棒的第一根木棍失败说明这根木棍没地方放则当前状态一定失败直接回溯不要往下搜了 (4) 如果是木棒的最后一根木棍失败这里的意思是往下dfs找不到解则当前状态一定失败因为放入比这根木棍小的木棍拼接起来的也一定找不到解直接回溯不要往下搜了
代码
#include bits/stdc.husing namespace std;const int N 70;int n;
int w[N], sum, length; // w[i]:每根小棍长度 sum:所有小棍总长度 length:每组总和
bool st[N]; // 小棍有没有用过bool dfs(int u, int s, int start) // u:当前枚举到哪根大棍 s:当前大棍长度 start:开始位置
{if (u * length sum) return true; // 符合条件if (s length) return dfs(u 1, 0, 0); // 这根木棍长度已达要求开下一根木棍// 优化3(1):从start开始枚举for (int i start; i n; i ) // 从start开始遍历木棍{if (st[i]) continue; // 已遍历if (s w[i] length) continue; // 可行性剪枝st[i] true; // 更改状态if (dfs(u, s w[i], i 1)) return true; // 下一层遍历st[i] false; // 恢复现场// 优化3(3):开头不行就一定不行if (!s) return false;// 优化3(4):结尾不行就一定不行if (s w[i] length) return false;// 优化3(2):等长直接略过int j i;while (j n w[j] w[i]) j ;i j - 1;}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);while (cin n, n){memset(st, false, sizeof st);sum 0;for (int i 0; i n; i ){cin w[i];sum w[i];}// 优化2搜索顺序sort (w, w n);reverse(w, w n);length 1;while (1){// 优化1:必须是整数倍if (sum % length 0 dfs(0, 0, 0)){cout length \n;break;}length ;}}
}生日蛋糕
原题链接
7 月 17 日是 Mr.W 的生日ACM-THU 为此要制作一个体积为 Nπ 的 M 层生日蛋糕每层都是一个圆柱体。
设从下往上数第 i 层蛋糕是半径为 Ri高度为 Hi 的圆柱。
当 i M iM iM 时要求 R i R i 1 RiRi1 RiRi1 且 Hi Hi1。
由于要在蛋糕上抹奶油为尽可能节约经费我们希望蛋糕外表面最下一层的下底面除外的面积 Q 最小。
令 Q S π QSπ QSπ 请编程对给出的 N 和 M找出蛋糕的制作方案适当的 Ri 和 Hi 的值使 S 最小。
除 Q 外以上所有数据皆为正整数。
输入格式
输入包含两行第一行为整数 N表示待制作的蛋糕的体积为 Nπ。
第二行为整数 M表示蛋糕的层数为 M。
输出格式
输出仅一行是一个正整数 S若无解则 S0。
数据范围
1 ≤ N ≤ 10000, 1 ≤ M ≤ 20
输入样例
100
2输出样例
68题意
多层蛋糕给出总体积总层数可以自定义每一层半径和高度使得从上往下看的总面积和总侧面积之和最小求最小值
思路
首先明确我们的目的是让 2 * Rm * hm 2 * Rm-1 * hm-1 … 2 * R1 * h1 Rm2 最小省去了所有的 π π π
优化
优化搜索顺序分支少的先搜从大到小枚举 (1) 要先搜面积大的因此自底向上搜 (2) 半径是平方级别高是一次方半径对体积影响更大因此先枚举半径可行性剪枝 (1) 设从上往下为1-m层第 u 层的半径记为 Ru一定比 u 大且比 Ru1 - 1 小同时我们设第 u 层下方的所有体积为 V那么前 u 层的体积就是 n − V n - V n−V即有 n − V R u 2 h u n - V R_u^2h_u n−VRu2hu放缩后有 R u n − V R_u \sqrt{n - V} Run−V 据此得到 u R u m i n { R u 1 − 1 , n − V } u R_u min\{R_{u1}-1, \sqrt{n-V}\} uRumin{Ru1−1,n−V } (2) 同时Hu也u且比 Hu1小 n − V R u 2 h u n - V R_u^2h_u n−VRu2hu放缩后有 h u n − V R 2 h_u \frac{n-V}{R^2} huR2n−V 据此得到 u h u m i n { h u 1 − 1 , n − V R 2 } u h_u min\{h_{u1}-1, \frac{n-V}{R^2}\} uhumin{hu1−1,R2n−V}最小体积是半径和高都取1时因此可以预处理一下前 u 层的体积最小值 m i n v ( u ) minv(u) minv(u)和表面积最小值 m i n s ( u ) mins(u) mins(u)需要满足以下两个条件才有往下搜的必要否则直接回溯 V m i n v ( u ) n Vminv(u)n Vminv(u)n s m i n s ( u ) a n s smins(u)ans smins(u)ans已知 n − V ∑ k 1 u R k 2 h k n-V\sum_{k1}^{u}R_k^2h_k n−V∑k1uRk2hk 并且 S 1 → u ∑ k 1 u 2 R k h k 2 R u 1 ∑ k 1 u R u h R u 1 2 R u 1 ∑ k 1 u R u 2 h S_{1\rightarrow u}\sum_{k1}^{u}2R_kh_k\frac{2}{R_{u1}}\sum_{k1}^{u}R_uhR_{u1}\frac{2}{R_{u1}}\sum_{k1}^{u}R_u^2h S1→u∑k1u2RkhkRu12∑k1uRuhRu1Ru12∑k1uRu2h 因此 S 1 → u 2 ( n − V ) R u 1 S_{1\rightarrow u}\frac{2(n-V)}{R_{u1}} S1→uRu12(n−V) 所以当 s 2 ( n − V ) R u 1 a n s s\frac{2(n-V)}{R_{u1}}ans sRu12(n−V)ans时已经不可能是最优解了直接回溯
(好难…疯掉TAT
代码
#include bits/stdc.husing namespace std;const int N 25, inf 1e9;int n, m;
int minv[N], mins[N]; // 分别表示每一层及该层上方的最小体积和最小表面积
int R[N], H[N]; // 表示每一层的半径和高
int ans inf;void dfs(int u, int v, int s) // u:当前层数 v:当前体积 s:当前表面积
{if (v minv[u] n) return; // 优化3if (s mins[u] ans) return; // 优化3if (s 2 * (n - v) / R[u 1] ans) return; // 优化4if (!u) //已全部搜完{if (v n) ans s;return;}// 优化1:从大到小枚举for (int r min(R[u 1] - 1, (int)sqrt(n - v)); r u; r -- ) // 优化2for (int h min(H[u 1] - 1, (n - v) / r / r); h u; h -- ) // 优化2{int t 0;if (u m) t r * r; // 如果是最底层要加上底面积R[u] r, H[u] h; // 更新RHdfs(u - 1, v r * r * h, s 2 * h * r t);}
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin n m;// 打表做出minv minsfor (int i 1; i m; i ){minv[i] minv[i - 1] i * i * i;mins[i] mins[i - 1] 2 * i * i;}R[m 1] H[m 1] inf; // 设置哨兵dfs(m, 0, 0);if (ans inf) ans 0; // 无满足要求的情况cout ans \n;
}
