9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

NOIP贪心法



贪心法

概念
?

?

?

贪心法是沿着一种固定的策略一直走下去的算 法 与动态规划和搜索的区别是,动态规划和搜索 在一个阶段都会考虑所有可能出现的状态,而 贪心只需要知道哪个状态是最优 可以用贪心的条件是满足每步都最优,总结果 也最优

例1、删数问题

/>【问题描述】键盘键入一个高精度的正整数n(≤240位), 去掉其中任意s个数字后剩下的数字按原左右次序将组 成一个新的正整数。编程对给定的n和s,寻找一种方案, 使得剩下的数字组成的新数最小。 输入:n s

输出:最后剩下的最小数
【样例输入 】 178543 4

【样例输出】

13

【问题分析】
如何决定哪s位被删除呢?是不是最大的s个数字? 贪心策略:

每一步总是选择一个使剩下的数最小的数字删去,
即按高位到低位的顺序搜索,若各位数字递增,则删 除最后一个数字;否则,删除第一个递减区的首字符。

然后回到串首,按上述规则再删下一个数字。重复以
上过程s次为止。 如何寻找递减区间首字符?

例2、取数游戏
【问题描述】给出2n(≤100)个自然数(数小于等于 30000)。游戏双方分别为A方(计算机方)和B方(对 弈的人)。只允许从数列两头取数,A先取,然后双方 依次轮流取数。取完时,谁取得的数字总和最大为取 胜方;若双方和相等,属于A胜。试问A方可否有必胜 的策略? 输入:键盘输入n及2n个自然数 输出:共3n+2行,前3n行为游戏经过,每3行分别为A方 所取的数和B方所取的数,及B方取数前的提示(L/R— 左端或右端)。最后2行分别为A方所取得数的和与B方 所取得数的和。

【问题分析】
n=4,自然数列:7 9 3 6 4 2 5 3 A每次取数列两头较大的那个数

游戏者:每次取数列两头较大的那个数

A:7+3+4+5=19

B:9+6+2+3=20

A方输

【问题分析】
n=4,自然数列:7 9 3 6 4 2 5 3 若A取走偶位置的数,则剩下两端数都处于奇位置; 若A取走奇位置的数,则剩下两端数都处于偶位置; 既无论B如何取法,A方既可以取走奇位置的所有数,也 可以取走偶位置的所有数。 贪心策略: 让A方取走“数和较大的奇(或偶)位置上的所有 数”,则A方胜。既让A方取奇偶位置中数和较大的一半 数。 设置奇偶位置标志,j=0表示偶数位置数和较大,A 取偶数位置上的所有数;j=1表示奇数位置数和较大, A 取偶数位置上的所有数。

例3、部分背包问题
给定一个最大载重量为M公斤的卡车和N种食品,有食盐,白 糖,大米等。已知第i种食品的最多拥有Wi公斤,其商品价值为Vi 元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总 价值最大。 输入文件(truck.in) 第一行两个数M,N,为卡车载重和食品种数。 第二行是N个数,第i个数表示第i种食品的单价 第三行也是N个数,第i个数表示第i种食品的最大拥有量 输出文件(truck.out)

只有一行,为装入卡车的物品总价值。 分析:要使得总价值最大,就应该首选那些单价较大的商品,即 按商品价值Vi从大到小排序,直到满足卡车的最大载重(背包大 小),当然还有一个条件就是每种食品最后只能拥有Wi公斤。

算法框架
读入数据;
按vi从大到小排序; i:=1;

Repeat
if M=0 then Break; {卡车已装满} if M>=Wi

then Begin 将第i种食品全部装入卡车;M:=M-Wi;End
else Begin 将M重量的食品i装入卡车;M:=0;End; i:=i+1; {选择下一种商品}

Until (M<=0) or (i<=N);

0-1背包问题
【问题描述】有一容量为weight的背包。现要从n件物品 中选取若干装入背包中,每件物品i的重量为w[i],价值 为p[i]。定义一种可行的背包装载为:背包中物品的总 重量不能超过背包的容量,并且一个物品要么全部选取, 要么不选取。定义最佳装载是指所装入的物品价值最高, 并且是可行的背包装载。 【样例输入】11 4 2 4 6 7 6 10 12 13 【样例输出】0 1 0 1 {weight} {n} {w[i]} {p[i]}

23

方案1:选价值大的
观察下面这一组数据: 105 3 20 15 15 100 10 10
按照这个方案,只能得到价值为20,但是事实上还 可以选择装入后两种动物得到价值30。

方案2:选择重量轻的
观察下面一组数据: 25 2 5 10 10 20
显然按照这种策略,只能装入第一种动物,价值为5,实 际上真正的最佳方案结果是10。

方案3:选择价值重量比(Vi / Wi)最大的
观察下面一组数据: 100 3 80 100 150 40 50 70
按照这种策略,三种动物的Vi/Wi分别为2,2,2.14。当然, 首先选150,此时卡车已不能装入其他动物,但是真正的最 优解是180。

例4、旅行家预算(NOIP1999 高中组第3题 )
【问题描述】一个旅行家想驾驶汽车以最少的费用,从 一个城市到另一个城市(假设出发时邮箱是空的)。 给定两城市之间的距离Dic1,汽车邮箱的容量C(以 升为单位),每升汽油能行驶的距离为Dic2,出发 时每升汽油的价格为P。沿途有n(1≤n ≤100 )个 加油站,油站i离出发点的距离为di,该油站每升汽油的 价格为pi(i=1,2,…,n).请编程输出完成任务最小的 费用,计算结果四舍五入至小数点后两位,如果无法 到达目的地,则输出“No solution”。

输入:
输入文件名为oil.in,共n+1行,第1行为:Dic1 C Dic2 P n,以下n行,其中第i+1( 1≤ i ≤ n)行 的数据均有3个,分别为:油站号i,该油站距出发点的 距离di,该油站每升汽油的价格Pi。每个数据之间用一 个空格隔开。 输出:输出文件oil.out,仅一行,表示最少费用。 【样例输入】275.6 11.9 27.4 2.8 2 1 102.0 2.9

2

220.0

2.2

【样例输出】26.95

分析:
题目要求从起点到终点的最小花费,又给了加油站的位置 与油费,明显贪心法,即让花费一直最小。 贪心思路: 1.如果在能到达的加油站中,油费有比当前加油站便宜 的,就到一个距离最近且油费比当前加油站便宜的加 油站去,在当前加油站加上刚好能到那个加油站的油 ,使到达加油站时油用光。 2.如果在能到达的加油站中,油费没有比当前加油站便 宜的,那就在此加油站加满油,然后开到能到达的加 油站中油费最小的加油站去。 一直循环下去,当能到达终点了,并且后面的站中油费 没有更小的了,这就是最终答案。 当找不到加油站了,即无解

分析:
设出发城市为0站,目的城市为n+1站。汽车目前在i站 (0≤ i ≤ n),应加多少油,驶往哪一站可使得整个行程的 花费最少? 【贪心策略】下一个目的站的单位油价尽可能低于i站,若所 有可达油站的单位油价都高于i站的话,则下一个目的站 的单位油价亦应该尽可能的便宜。在i站所有可到的油站 j(dj-di ≤C*Dic2,i+1≤j≤n+1)中,计算以下油站号: min1:单位油价低于i站且距离最近(以最小代价到达)的 一个油站。 Min2:在由i站直接可达的所有油站中,单位油价最便宜( 但高于i站)的一个油站。



更多相关文章:
全国青少年信息联赛(noip)大纲
全国青少年信息联赛(noip)大纲_其它课程_高中教育_教育专区。全国青少年信息学奥林...数理逻辑) 算法处理 2.分治思想 3.模拟法 4.贪心法 5.简单搜索算法(深度...
noip2008普及组复赛试题(附题解)
全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 全国信息学奥林匹克联赛(NOIP...[i]记录如果在第 j 列加通道,可以分割多少对调皮 学生,最后贪心法输出分割学生...
Noip常用算法大全
Noip 常用算法大全一、数论算法 1.求两数的最大公约数 function gcd(a,b:...{prim} B.Kruskal 算法:(贪心) 按权值递增顺序删去图中的边,若不形成回路则...
历届NOIP搜索算法全集
历届NOIP 搜索算法全集 转自:oifans 用动态规划来解背包问题 在历届 NOIP 竞赛...算法分析:如果采用贪心法,则先取价值最大的 10,消耗了容积 8,下面只能取容积...
noip算法总结2016
noip算法总结2016_学科竞赛_高中教育_教育专区。noip算法总结2016 ...如果某次更新 后这个条数>n-1 则存在负权环 堆+迪杰斯特拉则是用了贪心的思想...
NOIP2011第十七届初赛Pascal普及组试题与答案(Word)
NOIP2011第十七届初赛Pascal普及组试题与答案(Word)_学科竞赛_初中教育_教育专区...当探索到某一步时, B、枚举法 C、动态规划 D、贪心法 发现原先选择并不优...
NOIP2007普及组解题报告
NOIP 2007 普及组解题报告 1、 奖学金 (scholar.pas/c/cpp) 、 【问题描述...80<=w<=200 【试题分析】 试题分析】 贪心法,先排序,然后按以下贪心策略: ...
noip信息竞赛100个基本算法
noip信息竞赛100个基本算法_理学_高等教育_教育专区。算法noip 信息竞赛 100 个...{prim} B.Kruskal 算法:(贪心) 按权值递增顺序删去图中的边,若不形成回路则...
NOIP《 数据结构》练习题及答案
NOIP《 数据结构》练习题及答案_学科竞赛_初中教育_教育专区。NOIP 数据结构复习...A.回溯法 B.枚举法 c.动态规划 D.贪心法 59.近20年来,许多计算机专家都...
NOIP2008普及组复赛试题与解题报告
NOIP 2008 普及组解题报告一、ISBN 号码(isbn.pas/c/cpp) 【问题描述】 每...[i]记录如果在第 j 列加通道,可以分割多少对调皮学生,最后贪心法输出分割学生...
更多相关标签:
贪心法    贪心法解决01背包    区间调度问题 贪心法    贪心法 最大整数    贪心法骑士问题    贪心法解决背包问题    贪心法 01背包    贪心法求最短路径    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图