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站)的一个油站。



更多相关文章:
贪心算法经典例题
贪心算 法的基本思想是找出整体当中每个小的局部的最优解, 并且将所有的 这些...例 2 (NOIP1998tg)设有 n 个正整数,将他们连接成一排,组成 一个最大的多...
贪心算法经典例题
我们看看下面的例子 例 1 均分纸牌(NOIP2002tg) [问题描述] 有 N 堆纸牌,...利用贪心算法解题,需要解决两个问题: 一是问题是否适合用贪心法求解。我们看一...
贪心法
第5讲 回溯法专题讲座 编... 37页 1财富值 NOIP基础算法综合---分治与... 82页 免费 贪心算法背包问题 2页 1财富值如要投诉违规内容,请到百度文库投诉中心...
NOIP2002-2005解题报告
NOIP 讲义一、NOIP2002 题一:均分纸牌(NOIPG1)【问题描述】有 N 堆纸牌,...(10,10,10),通过观察,我们发现,用贪心法和后一种正确的方 法所移动的牌是...
全国青少年信息联赛(noip)大纲
全国青少年信息联赛(noip)大纲_其它课程_高中教育_教育专区。全国青少年信息学奥林...模拟法 4.贪心法 5.简单搜索算法(深度优先 广度优先)搜索中的剪枝 6.动态...
noip2008普及组复赛试题(附题解)
全国信息学奥林匹克联赛(NOIP2008)复赛 普及组 全国信息学奥林匹克联赛(NOIP...[i]记录如果在第 j 列加通道,可以分割多少对调皮 学生,最后贪心法输出分割学生...
noip算法总结2016
noip算法总结2016_学科竞赛_高中教育_教育专区。noip算法总结2016 ...所以用贪心法解题需要丰富的经 验,正确的“题感” ,胆大心细才能搞出来 由于...
noip2011普及组初赛试题与答案
noip2011普及组初赛试题与答案_IT/计算机_专业资料。noip2011普及组初赛试题与...A、回溯法 B、枚举法 C、动态规划 D、贪心法 18、1956 年( )授予肖克利(...
NOIP初赛资料
NOIP初赛复习——一些基本... 23页 免费如要投诉违规内容,请到百度文库投诉中心...模拟法 4.贪心法 5.简单搜索算法(深度优先 广度优先)搜索中的剪枝 6.动态...
noip信息竞赛100个基本算法
noip信息竞赛100个基本算法_理学_高等教育_教育专区。算法noip 信息竞赛 100 个...Dijkstra 算法: 类似标号法,本质为贪心算法。 var a:array[1..maxn,1..maxn...
更多相关标签:
noip 贪心    noip贪心骗分    贪心法    贪心法解决01背包    贪心法优缺点    贪心法 背包问题    贪心法解决背包问题    dijkstra贪心法    

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

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