2023CSP初赛备考复习 || 搜索与回溯

搜索

索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法

常见2种搜索遍历方式：宽度优先搜索(Breadth First Search)、深度优先搜索DFS (Depth-First-Search )

宽度优先搜索

宽度优先搜索是一种基于队列的搜索算法。它从起始节点开始，逐层地向外扩展搜索，直到找到目标节点或者搜索完整张图.

深度优先搜索

深度优先搜索是一种递归的搜索算法。它从起始节点开始，递归地访问每一个节点，直到找到目标节点或者搜索完整张图

搜索与回溯

是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。

回溯是搜索算法中的一种控制策略。

它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解

例1 可能体积

问题描述

给出n 件物品，每件物品有一个体积V[i] ，求从中取出若干件物品能够组成的不同的体积和有多少种可能

输入格式

第 1行1 个正整数，表示 n(n

第 2 行 n 个正整数，表示 V[i] (v[i]

输出格式

一行一个数，表示不同的体积和有多少种可能

输入样例

输出样例

大致思路

1 枚举一个方案时，从第1个物品开始，都可以选择和不选择，这种情况对结合有不同影响

2 第1个物品选择时，第2个物品也有选择和不选择2中方案，第1个物品不选择时，第2个物品也有选择和不选择2种方案。

3 继续处理第3个物品...n个物品

4 走到第n个物品时回溯到第n-1个物品，n-1个物品处理完，继续回溯到n-2个物品...

参考程序

例2 01背包

问题描述

有n件物品，每件物品的重量为w[i],价值为c[i]. 现在需要选出若干件物品放入一个容纳重量为V的背包中，使得在选入背包的物品重量和不超过容纳重量V的前提下，让背包中物品的价值之和最大，求最大价值

输入格式

第 1行1 个正整数，表示 n(1

第 2 行 n 个正整数，表示 w[i]

第 3 行 n 个正整数，表示 c[i]

输出格式

一行一个数，最大价值

输入样例

输出样例

大致思路

1 安排把物品一件一件放入背包，放入物品的由于选择价值最高，可以选择中间某件物品不放入形成一种方案，放入形成一种方案，最后结果对比，取价值高的

2 每件物品都可以选择放入和不放入，所以可以保证枚举所有情况，取价值最高的

3 每件物品都可以选择放入 和不放入背包 ，因此需要处理n次，第n+1次进行，判断取最大值

参考程序

例3 全排列

问题描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字

输入格式

一个整数 n (1

输出格式

由1~n 组成的所有不重复的数字序列，每行一个序列

每个数字保留5个场宽

输入样例

输出样例

大致思路

1 把n个数字填入输入row中，一位一位填，一直填到n位

2 再深入进行1位为n+1，此时输出本方案即可

3 一次路径结束后，回溯到上一位继续填入相应数字，继续深入到n+1位输出

4 输出过程由于本次过程中数字不能重复，需要一个数字used记录本次已填的数字

参考程序