《高中信息竞赛贪心算法ppt课件》由会员分享，可在线阅读，更多相关《高中信息竞赛贪心算法ppt课件（55页珍藏版）》请在装配图网上搜索。
1、 贪婪是一种解题战略贪婪是一种解题战略,也是一种解题思想也是一种解题思想 运用贪婪方法需求留意部分最优与全局最优的关系运用贪婪方法需求留意部分最优与全局最优的关系,选择当选择当前形状的部分最优并不一定能推导出问题的全局最优前形状的部分最优并不一定能推导出问题的全局最优 因此因此,利用贪婪战略解题利用贪婪战略解题,需求处理两个问题：需求处理两个问题：首先首先,确定问题能否能用贪婪战略求解；普通来说确定问题能否能用贪婪战略求解；普通来说,适用于贪婪战略求适用于贪婪战略求解的问题具有以下特点：解的问题具有以下特点：1.可经过部分的贪婪选择来到达问题的全局最优解。运用贪婪战略解可经过部分的贪婪选择来到
2、达问题的全局最优解。运用贪婪战略解题题,普通来说需求一步步的进展多次的贪婪选择。在经过一次贪婪选择之后普通来说需求一步步的进展多次的贪婪选择。在经过一次贪婪选择之后,原问题将变成一个类似的原问题将变成一个类似的,但规模更小的问题但规模更小的问题,而后的每一步都是当前看似而后的每一步都是当前看似最正确的选择最正确的选择,且每一个选择都仅做一次。且每一个选择都仅做一次。2.原问题的最优解包含子问题的最优解原问题的最优解包含子问题的最优解,即问题具有最优子构造的性质。即问题具有最优子构造的性质。在背包问题中在背包问题中,第一次选择单位质量最大的货物第一次选择单位质量最大的货物,它是第一个子问题的最优
3、它是第一个子问题的最优解解,第二次选择剩下的货物中单位分量价值最大的货物第二次选择剩下的货物中单位分量价值最大的货物,同样是第二个子问同样是第二个子问题的最优解题的最优解,依次类推。依次类推。其次其次,如何选择一个贪婪规范？正确的贪婪规范可以得到问题的最优解如何选择一个贪婪规范？正确的贪婪规范可以得到问题的最优解,在确定采用贪婪战略处理问题时在确定采用贪婪战略处理问题时,不能随意的判别贪婪规范能否正确不能随意的判别贪婪规范能否正确,尤其尤其不要被外表上看似正确的贪婪规范所迷惑。在得出贪婪规范之后应给予严不要被外表上看似正确的贪婪规范所迷惑。在得出贪婪规范之后应给予严厉的数学证明。厉的数学证明。
4、【分析】：由于排队时【分析】：由于排队时,越靠前面的计算的次数越多越靠前面的计算的次数越多,显然越显然越小的排在越前面得出的结果越小小的排在越前面得出的结果越小(可以用数学方法简单证明可以用数学方法简单证明),所以这道题可以用贪婪法解答所以这道题可以用贪婪法解答,根本步骤：根本步骤：1.将输入的时间按从小到大排序；将输入的时间按从小到大排序；2.将排序后的时间按顺序依次放入每个水龙头的队列中；将排序后的时间按顺序依次放入每个水龙头的队列中；3.统计，输出答案。统计，输出答案。Description：给出：给出2n(n=100)个自然数个自然数(小于等于小于等于30000)。将这将这n个自然数排
5、成一列，游戏双方个自然数排成一列，游戏双方A和和B从中取数，只允许从中取数，只允许从两端取数。从两端取数。A先取，然后双方轮番取数。取完时，谁获得先取，然后双方轮番取数。取完时，谁获得数字总和最大为取胜方；假设双方和相等，属数字总和最大为取胜方；假设双方和相等，属B胜。试问胜。试问A方方能否有必胜战略？能否有必胜战略？Input：两行，第一行一个整数：两行，第一行一个整数n；第二行有；第二行有2*n个自然数。个自然数。Output：第一行：假设：第一行：假设A有必胜战略，那么输出有必胜战略，那么输出yes，否那，否那么输出么输出no Sample Input 47 9 3 6 4 2 5 3S
6、ample Output：yes 运用贪婪战略解题时，有的标题有不止一种能够的贪婪规运用贪婪战略解题时，有的标题有不止一种能够的贪婪规范，但不一定每种贪婪规范都可以得到正确的结果。因此，范，但不一定每种贪婪规范都可以得到正确的结果。因此，在运用贪婪法时，一定要仔细分析，选择恰当的贪婪规范。在运用贪婪法时，一定要仔细分析，选择恰当的贪婪规范。Description 牛奶包装是一个如此低利润的生意牛奶包装是一个如此低利润的生意,所以尽能够低的控制初级产品所以尽能够低的控制初级产品(牛奶牛奶)的价钱的价钱变的非常重要。请协助高兴的牛奶制造者变的非常重要。请协助高兴的牛奶制造者(merry milk
7、makers)以能够的最廉价的方以能够的最廉价的方式获得他们所需的牛奶。高兴的牛奶制造公司从一些农民那购买牛奶，每个农民卖式获得他们所需的牛奶。高兴的牛奶制造公司从一些农民那购买牛奶，每个农民卖给牛奶制造公司的价钱不一定一样。而且给牛奶制造公司的价钱不一定一样。而且,如一只母牛一天只能消费一定量的牛奶如一只母牛一天只能消费一定量的牛奶,农民每一天只需一定量的牛奶可以卖。每天农民每一天只需一定量的牛奶可以卖。每天,高兴的牛奶制造者从每个农民那购买一高兴的牛奶制造者从每个农民那购买一定量的牛奶定量的牛奶,少于或等于农民所能提供的最大值。少于或等于农民所能提供的最大值。给出高兴牛奶制造者的每日的牛奶
8、需求给出高兴牛奶制造者的每日的牛奶需求,连同每个农民的可提供的牛奶量和每加连同每个农民的可提供的牛奶量和每加仑的价钱仑的价钱,请计算高兴的牛奶制造者所要付出钱的最小值。留意请计算高兴的牛奶制造者所要付出钱的最小值。留意:每天农民消费的牛每天农民消费的牛奶的总数对高兴的牛奶制造者来说足够的。奶的总数对高兴的牛奶制造者来说足够的。Input 第第 1 行行:二个整数二个整数,n 和和 m。第一个数值第一个数值,n,(0=n=2,000,000)是高兴的牛奶制造者的一天需求牛奶的数量。是高兴的牛奶制造者的一天需求牛奶的数量。第二个数值第二个数值,m,(0=m=5,000)是他们能够从农民那买到的数目
9、。是他们能够从农民那买到的数目。第第 2 到到 m+1 行行:每行二个整数每行二个整数,pi 和和 ai。pi(0=pi=1,000)是农民是农民 i 牛奶的价钱。牛奶的价钱。ai(0=ai=2,000,000)是农民是农民 i 一天能卖给高兴的牛奶制造者的牛奶数量。一天能卖给高兴的牛奶制造者的牛奶数量。Output：单独的一行包含单独的一个整数，表示高兴的牛奶制造者拿到所需的牛奶：单独的一行包含单独的一个整数，表示高兴的牛奶制造者拿到所需的牛奶所要的最小费用所要的最小费用 Description：在黑板上写了：在黑板上写了N个正整数组成的一个数列，进展如下操作：个正整数组成的一个数列，进展如
10、下操作：每次擦去其中的两个数每次擦去其中的两个数a和和b，然后在数列中参与一个数，然后在数列中参与一个数ab1，如此下去，如此下去直至黑板上直至黑板上 剩下一个数，在一切按这种操作方式最后得到的数中，最大的剩下一个数，在一切按这种操作方式最后得到的数中，最大的为为max，最小的为，最小的为min，那么该数列的极差定义为那么该数列的极差定义为Mmaxmin。请他编程，对于给定的数列，计算极差。请他编程，对于给定的数列，计算极差。Input：第一个数：第一个数N表示表示 正整数序列长度正整数序列长度0N50000，随后是，随后是N个正整数。个正整数。N为为0表示输入终了。表示输入终了。Output
11、：计算极差：计算极差Sample Input 31230Sample Output：2【试题分析】我们要使挪动次数最少，就是要把浪费降至零。【试题分析】我们要使挪动次数最少，就是要把浪费降至零。经过对详细情况的分析，可以看出在某相邻的两堆之间挪动两经过对详细情况的分析，可以看出在某相邻的两堆之间挪动两次或两次以上，是一种浪费，由于我们可以把它们合并为一次次或两次以上，是一种浪费，由于我们可以把它们合并为一次或零次。因此，我们将相邻两堆间的挪动次数限定在一次或零或零次。因此，我们将相邻两堆间的挪动次数限定在一次或零次。次。53 5 8 7 106 2 1 4 9【样例输出】：【样例输出】：34算法流程如下：算法流程如下：for I:=1 to N do 求求M数组数组 if AI BI then MI:=AI else MI:=BI；将将M从小到大排序；从小到大排序；S:=1;T:=N;首位指针初始化首位指针初始化for I:=1 to N do if 对于第对于第I小的工序小的工序J，假设，假设AJ BJ then begin OrderS:=J;将工序将工序J插在加工序列的前面插在加工序列的前面 S:=S+1;end else begin OrderT:=J;将工序将工序J插在加工序列的后面插在加工序列的后面 T:=T-1;end;罚款问题罚款问题
高中信息竞赛贪心算法ppt课件
