大理做网站哪家好,网站投入费用,网站开发经济可行性分析,海兴做网站价格这篇文章是一年前写的 走进“深度搜索基础训练“#xff0c;踏入c算法殿堂#xff08;一#xff09;和 走进“深度搜索基础训练“#xff0c;踏入c算法殿堂#xff08;二#xff09;的重编版。 希望以此#xff0c;唤起对那位故人的回忆。 小航走入赛场#xff0c;比赛… 这篇文章是一年前写的 走进“深度搜索基础训练“踏入c算法殿堂一和 走进“深度搜索基础训练“踏入c算法殿堂二的重编版。 希望以此唤起对那位故人的回忆。 小航走入赛场比赛即将开始……
主持人欢迎来到深度搜索基础训练的比赛现场。首先感谢全心全意为我们挖坑、绞尽脑汁出难题的出题老师们然后感谢古灵精怪的农夫John最后感谢c……废话少说比赛开始
小航看向第一题…… 【搜索与回溯算法】N皇后问题
小航看到题面 时间限制: 1000 ms 空间限制: 262144 KB 具体限制 题目描述 在一个nXn的国际象棋棋盘上放置n(n12)个皇后使它们不能互相攻击即任意两个皇后不能在同一行、同一列或同一对角线上。试求出所有方法。 输入 输入一个数n .(n12) 输出 输出所有的排列方案总数。 样例输入 4 样例输出 2 小航想到思路
1.合法检查
即需要判断
1是否处于同一列中
2是否在左斜线上行 列的值不可相等绝对值
3是否在右斜线上列 - 行的值不可相等绝对值
4为何不需要判断每一行
因为在DFS中x已经代表了行根据算法每一行也只有一个所以无需判断。 3.DFS搜索
1结束条件当前行数 皇后总数即最后一行已经成功放入皇后
2循环一行中的每一个位置若不发生攻击事件可将皇后放入该位置
3继续下一行的搜索即传入的参数为当前行数 1 小航写道代码
#includeiostream
using namespace std;
int a[105],b[105],c[105],n,s;//数组a为判断列是否放置皇后b、c都是判断对角线是否放置皇后
void dg(int x)//循环行
{for(int i1;in;i)//循环列{if(a[i]!1b[xi]!1c[i-xn-1]!1){a[i]1;b[ix]1;c[i-xn-1]1;//上面两步及这步都是标记if(xn){s;//当放到最后一个方案数增加}else{dg(x1);//进入下一行放置} a[i]0;b[ix]0;c[i-xn-1]0;//回溯} }
}
int main()
{cinn;dg(1);couts;//输出方案数
}
小航很快就把第一道题做完了准备迎接下一题…… 【搜索与回溯算法】装载问题 (Standard IO) 时间限制: 1000 ms 空间限制: 262144 KB 具体限制 题目描述 有一批共n个集装箱要装上艘载重量为c的轮船其中集装箱i的重量为wi。找出一种最优装载方案将轮船尽可能装满即在装载体积不受限制的情况下将尽可能重的集装箱装上轮船。 输入 第一行有2个正整数n和c。n是集装箱数c是轮船的载重量。接下来的1行中有n个正整数表示集装箱的重量。 输出 将计算出的最大装载重量输出 样例输入 5 10
7 2 6 5 4 样例输出 10 数据范围限制 n35c1000 “其实这就是一道超级简单的背包问题可以用递归解决。”小航想“建立一个临时重量和最终重量搜索每一个数字选与不选只要搜索后的结果大于最终结果就赋值。”
#includeiostream
using namespace std;
int n,c,w[40],s;
void dfs(int x,int sx)//第x个物品sx为临时重量
{if(xn){if(sxs) ssx;//赋值return;}else{if(sxw[x]c)//如果装入此物品还没超载的话……{dfs(x1,sxw[x]);//装入此物品并搜索下一件物品}dfs(x1,sx);//在不装入此物品的情况下搜索下一件物品}
}
int main()
{cinnc;for(int i1;in;i) cinw[i];dfs(1,0);couts;//输出最终重量
} 但是。小航后来知道这个看似简单的程序险些超时。他不甘心修改了一下
#includebits/stdc.h
using namespace std;
int n,c,w[40],s,b[40],ms0;
void dg(int x)
{if(sc){if(sc){printf(%d,s);exit(0);}s-w[x-1];if(mss)mss;sw[x-1];}else if(xn){if(mss)mss;}else{sw[x];dg(x1);s-w[x];dg(x1);}return;
}
int main()
{scanf(%d%d,n,c);for(int i0;in;i)scanf(%d,w[i]);dg(0);printf(%d,ms);return 0;
}
#includebits/stdc.h using namespace std; int n,c,w[40],s,b[40],ms0; void dg(int x) { if(sc) { if(sc) { printf(%d,s); exit(0); } s-w[x-1]; if(mss) mss; sw[x-1]; } else if(xn) { if(mss) mss; } else { sw[x]; dg(x1); s-w[x]; dg(x1); } return; } int main() { scanf(%d%d,n,c); for(int i0;in;i) scanf(%d,w[i]); dg(0); printf(%d,ms); return 0; } 这样运行时间缩短了不少。 之后下一题又映入眼帘……
