2022年2022年历届NOIP搜索算法全集 .pdf

《2022年2022年历届NOIP搜索算法全集 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年历届NOIP搜索算法全集 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、历届 NOIP 搜索算法全集转自：oifans用动态规划来解背包问题在历届 NOIP 竞赛中，有 4 道初赛题和5 道复赛题均涉及到背包问题，所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N 类不同大小与价值的物品，但小偷只有一个容积为M 的背包来装东西， 背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。如有 4 件物品，容积分别为：3 4 5 8 对应的价值分别为：4 5 7 10 小偷背包的载重量为：12 则取编号为1 2 3 的物品，得到最大价值为16。算法分析：如果采用贪心法，则先取价值最大的10，消耗了容积8，下面只能取容积为4的物品，得到

2、价值5，这样总价值是15，这不是最优解，因此贪心法是不正确的。采用穷举法，用一个B 数组来表示取数的标记，当B=0 时表示第i 件物品不取，当B=1 时表示第 i 件物品已取，初始化全部取0，以下算法是从后面的物品开始取起，通过B 数组的取值把 15 种取法全部穷举出来，价值MAX 初始化为0。B0 B1 B2 B3 B4 0 0 0 0 0 初始化 0 0 0 0 1 取第 4 件物品，容积为8，不超，价值为10，将 MAX 替换为 10 0 0 0 1 0 取物品3，容积为5，不超，价值为7，不换0 0 0 1 1 取物品3、 4，容积为 13，超0 0 1 0 0 取物品2，容积为4，不

3、超，价值为5，不换0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 1 1 0 这是最佳方案0 1 1 1 1 1 0 0 0 0 当 B0 1 时停止， B0称为哨兵生成 B 数组中数据的方法如下：fillchar(b,sizeof(b),0); while b0=0 do begin j:=n; while bj=1 do dec(j); bj:=1; for i:=j+1 to n do b:=0; end；小结：以上每件物品只能取1 件，所以取法只有0 和 1 两种情况，我们称之为0、1 背包，算法的时间复杂度为O（2N） ，在 1 秒内 N 只能做到20。例 1：选

4、数（ NOIP2002 初中组复赛第2 题）问题描述 :已知n 个整数x1,x2, ,xn ，以及一个整数k（kn） 。从 n 个整数中任选k 个整数相加， 可分别得到一系列的和。例如当n=4，k3，4 个整数分别为3，7，12，19 时，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 可得全部的组合与它们的和为：3712=22 371929 71219 38 3121934。现在，要求你计算出和为素数共有多少种。例如上例，只有

5、一种的和为素数：371929。输入 ：键盘输入，格式为：n , k （1=n=20，kn）x1,x2 ，,xn （1=xi=5000000 ）n输出 ：屏幕输出，格式为：一个整数（满足条件的种数）。输入输出样例: 输入：4 3 3 7 12 19 输出：1 算法分析 :本题应用背包问题中取数的方法进行穷举，在取数的过程中，当B 数组中有K个 1 的时候将对应的K 个数相加，再判断是不是素数。主要程序段如下：readln(n,k); sum:=0; for i:=1 to n do read(a); fillchar(b,sizeof(b),0); while b0=0 do begin j:=

6、n; while bj=1 do dec(j); bj:=1; for i:=j+1 to n do b:=0; m:=0; for i:=1 to n do if b=1 then m:=m+1; 统计 1 的个数 if m=k then begin 计算此种取数方法得到的和S；if S 是素数then sum:=sum+1; end; end; 例 2：采药 (NOIP2005 初中组复赛第3 题) 【问题描述】辰 辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：

7、“ 孩子， 这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 【输入文件】输 入文件 medic.in 的第一行有两个整数T（ 1 = T = 1000 ）和 M（1 = M = 100 ） ，用一个空格隔开

8、， T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的M行每行包括两个在1 到 100 之间（包括1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out 包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【样例输入】70 3 71 100 69 1 1 2 【样例输出】3 【数据规模】对于 30%的数据， M = 10 ；对于全部的数据，M =time) and (price+countj-timecountj) then countj:=price+countj-time; end; j=ti

9、me 表示当前的容量能放入背包，price+countj-timecountj表示第 i 件物品的价值加上第i 件物品对于背包容量为j 时余下空间的最大价值大于当前背包容量为j 时的最大价值 writeln(countt); close(input); close(output); end. 例 3：开心的金明（NOIP2006 初中组复赛第2 题）题目较长，省略，本题与例2 相比，在比较时要先将价值乘以一个数，其余一样，但要注意的是：本题N 的范围是 =26，如果用0、1 背包穷举法在1 秒内只能过10 个点中的 8 个点。总结：采用动态规划的时间复杂度为O(n*m) ，范围比穷举法大多了，但也有弱点，当数据不是整数时，就不可使用；如果还要求出具体的取法，那也相当麻烦。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -