首页 历届NOIP搜索算法全集

历届NOIP搜索算法全集

举报
开通vip

历届NOIP搜索算法全集历届NOIP搜索算法全集 NOIP 算法分析:如果采用贪心法,则先取价值最大的10,消耗了容积8,下面只能取容积为4的 .... [数据结构] time,price数组分别用来存入时间和价值,count来存入背包的价值。 ... 算法,数据结构 专题技术 牛档搜索(Niudown.COM) 本文系牛档搜索(Niudown.COM)根据用户的指令自动搜索的结果,文中内涉及到的 资料均来自互联网,用于学习交流经验,作品其著作权归原作者所有。不代表牛档搜索Niudown.COM)赞成本文的内容或立场,牛档搜...

历届NOIP搜索算法全集
历届NOIP搜索算法全集 NOIP 算法分析:如果采用贪心法,则先取价值最大的10,消耗了容积8,下面只能取容积为4的 .... [数据结构] time,price数组分别用来存入时间和价值,count来存入背包的价值。 ... 算法,数据结构 专题技术 牛档搜索(Niudown.COM) 本文系牛档搜索(Niudown.COM)根据用户的指令自动搜索的结果,文中内涉及到的 资料均来自互联网,用于学习交流经验,作品其著作权归原作者所有。不代 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 牛档搜索Niudown.COM)赞成本文的内容或立场,牛档搜索(Niudown.COM)不对其付相应的法( 律责任! 历届NOIP搜索算法全集 oifans 用动态规划来解背包问题 转自:在历届NOIP竞赛中,有4道初赛题和5道复赛题均涉及到背包问题,所谓的背包问题,可 以描述如下:一个小偷打劫一个保 险箱,发现柜子里有N类不同大小与价值的物品,但小 偷只有一个容积为M的背包来装东西,背包问题就是要找出一个小偷选择所偷物品的组合, 以使偷走的物品总 价值最大。 如有4件物品,容积分别为: 3 4 5 8 对应的价值分别为: 4 5 7 10 小偷背包的载重量为:12 则取编号为1 2 3的物品,得到最大价值为16。 算法分析:如果采用贪心法,则先取价值最大的10,消耗了容积8,下面只能取容积为4的物品,得到价值5,这样总价值是15,这不是最优解,因此贪心法是不正确的。 采用穷举法,用一个B数组来表示取数的标记,当B=0时表示第i件物品不取,当B=1时表示第i件物品已取,初始化全部取0,以下算法是从后面的物品开始取起,通过B数组的取值把15种取法全部穷举出来,价值MAX初始化为0。 B[0] B[1] B[2] B[3] B[4] 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,不超,价值为5,不换} 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 …… 0 1 1 1 0 {这是最佳 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 } 0 1 1 1 1 1 0 0 0 0 {当B〔0〕=1时停止,B〔0〕称为哨兵} 生成B数组中数据的方法如下: fillchar(b,sizeof(b),0); while b[0]=0 do begin j:=n; while b[j]=1 do dec(j); b[j]:=1; for i:=j+1 to n do b:=0; end; 小结:以上每件物品只能取1件,所以取法只有0和1两种情况,我们称之为0、1背包,算法的时间复杂度为O(2N),在1秒内N只能做到20。 例1:选数(NOIP2002 初中组复赛第2题) [问题描述]:已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时, 可得全部的组合与它们的和为: 3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。 现在,要求你计算出和为素数共有多少种。 例如上例,只有一种的和为素数:3+7+19=29。 [输入]: 键盘输入,格式为: n , k (1<=n<=20,k<n) 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 b[0]=0 do begin j:=n; while b[j]=1 do dec(j); b[j]:=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题) 【问题描述】 辰 辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有 威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到 一个到处都 是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间, 每一株也有它自身的价值。我会给你一段时间,在这段时间 里,你可以采到一些草药。如 果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。” 如果你是辰辰,你能完成这个任务吗? 【输入文件】 输 入文件medic.in的第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一 个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M 行每行包括两个在1到100之间(包括1和100)的整 数,分别表示采摘某株草药的时间和这株草药的价值。 【输出文件】 输出文件medic.out包括一行,这一行只包含一个整数,表示在规定的时间内,可以采到的 草药的最大总价值。 【样例输入】 70 3 71 100 69 1 1 2 【样例输出】 3 【数据规模】 对于30%的数据,M <= 10; 对于全部的数据,M <= 100。 【算法分析】本题如果采用上述方法来解,只能将M算到20,而这里M〈=100,所以只能 拿30%的分数,比较好的算法是采用动态规划,为了能说清算法,现重新举一个例子,若 输入: 10 3 3 4 4 5 5 6 表示背包的容量是10,有3种物品。用一个数组用来表示背包容量与其最大价值的关系, 上例中设置一个数组count,用下标表示容量,初始化为0。然后按物品的顺序一一来统计此时的最大价值,每种药品对应各种背包容量时得到的最大价值为: 对于是第i件物品,背包容量为j时的最大价值Cmax(j)=MAX(Cmaxj,Pi+余下空间的最大价 值Cmax(j-i物品所占的空间)),如上例中,根据物品的不断增加,各容量背包得到的最大价 值不断替换: 容量 1 2 3 4 5 6 7 8 9 10 价值 序号 0 0 0 0 0 0 0 0 0 0 1 0 0 4 4 4 4 4 4 4 4 2 0 0 4 5 5 5 9 9 9 9 3 0 0 4 5 6 6 9 10 11 11 [数据结构] time,price数组分别用来存入时间和价值,count来存入背包的价值。 var time,price:array[1..100] of longint; t:longint; i,m,j:integer; count:array[0..1000] of longint; begin assign(input,'medic.in'); assign(output,'medic.out'); reset(input); rewrite(output); readln(t,m); for i:=1 to m do readln(time,price); fillchar(count,sizeof(count),0); for i:=1 to m do for j:=t downto 1 do begin if (j>=time) and (price+count[j-time]>count[j]) then count[j]:=price+count[j-time]; end; {j>=time表示当前的容量能放入背包,price+count[j-time]>count[j]表示第i件物品的价 值加上第i件物品对于背包容量为j时余下空间的最大价值大于当前背包容量为j时的最大 价值} writeln(count[t]); close(input); close(output); end. 例3:开心的金明(NOIP2006 初中组复赛第2题) 题目较长,省略,本题与例2相比,在比较时要先将价值乘以一个数,其余一样,但要注意 的是:本题N的范围是<=26,如果用0、1背包穷举法在1秒内只能过10个点中的8个点。 总结:采用动态规划的时间复杂度为O(n*m),范围比穷举法大多了,但也有弱点,当数据不是整数时,就不可使用;如果还要求出具体的取法,那也相当麻烦。
本文档为【历届NOIP搜索算法全集】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_650122
暂无简介~
格式:doc
大小:35KB
软件:Word
页数:9
分类:互联网
上传时间:2018-08-15
浏览量:31