贪心算法(1)讲解学习

贪心(tānxīn)算法第一页，共38页。贪心方法的基本(jīběn)思想贪心是一种(yīzhǒnɡ)解题策略，也是一种(yīzhǒnɡ)解题思想使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优利用贪心策略解题，需要解决两个问题：该题是否适合于用贪心策略求解如何选择贪心标准，以得到问题的最优解第二页，共38页。【引例】在一个N×M的方格(fānɡɡé)阵中，每一格子赋予一个数（即为权），规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。我们以2×3的矩阵为例：若按贪心(tānxīn)策略求解，所得路径为：1→3→4→6；若按动态规划求解(qiújiě)，所得路径为：1→2→10→6。第三页，共38页。贪心(tānxīn)法的特点1.贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。2.最优子结构性质：算法中每一次都取得了最优解(即局部最优解)，要保证(bǎozhèng)最后的结果最优，则必须满足全局最优解包含局部最优解。但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）第四页，共38页。【问题(wèntí)1】部分背包问题(wèntí)给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤(ɡōnɡjīn)，其商品价值为Vi元/公斤(ɡōnɡjīn)，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。【分析】因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益(shōuyì)越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：先将单位块收益(shōuyì)按从大到小进行排列，然后用循环从单位块收益(shōuyì)最大的取起，直到不能取为止便得到了最优解。第五页，共38页。【问题(wèntí)2】0/1背包问题(wèntí)给定一个最大载重量(zhòngliàng)为M的卡车和N种动物。已知第i种动物的重量(zhòngliàng)为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。【分析(fēnxī)】按贪心法：每次选价格最大的装载。很明显有反例：设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是80、100、150。第六页，共38页。贪心策略与其他(qítā)算法的区别1.贪心与递推：与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前(dāngqián)看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。2.贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。第七页，共38页。几个简单的贪心(tānxīn)例子第八页，共38页。贪心(tānxīn)策略第九页，共38页。例题(lìtí)1：删数问题键盘输入一个高精度的正整数n（n<=240位）,去掉其中任意s个数字(shùzì)后剩下的数字(shùzì)按照原来的次序将组成一个新的正整数。编程对给定的n和s,寻求一种方案,使得剩下组成的新数最小。【样例输入】178543182914【样例输出】13第十页，共38页。分析(fēnxī)由于正整数n的有效位数最大可达240位，所以可以采用字符串类型来存储n。那么，应如何来确定该删除哪s位呢？是不是只要删掉最大的s个数字就可以了呢？为了尽可能地逼近目标，我们(wǒmen)选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。第十一页，共38页。例题2：排队(páiduì)问题在一个(yīɡè)食堂，有n个人排队买饭，每个人买饭需要的时间为Ti，请你找出一种排列次序，是每个人买饭的时间总和最小。第十二页，共38页。【思路点拨】由题意可知，本题可以采用的贪心策略为：将n个人排队买饭的时间从小到大排序，再依次累加每人的买饭时间，即可得到最小的总和。由样例可知，排好序后的数据为(1,3,5,7,9,11)，每个人的买饭时间如下：T1=1T2=T1+t2=1+3=4T3=T2+t3=4+5=9T4=T3+t4=9+7=16T5=T4+t5=16+9=25T6=T5+t6=25+11=36总时间T=T1+T2+T3+T4+T5+T6=91用反证法证明如下：假设一个不排好序的n个人也能得到最优答案，比如把(1,3,5,7,9,11)中的3,5对调一下，得到的序列为(1,5,3,7,9,11)。对调后，3,5前后的1,7,9,11四个人的买饭时间不会有变化，关键的变化是3,5两个人。这时，5这个人的买饭时间为1+5，3这个人的买饭时间变为1+5+3，此时两个人的总买饭时间中，5被累加了2次，而原方案中是3被累加了2次，其他(qítā)一样。由此，两者相比较，可知有序的序列能得到最优的方案。对于其他(qítā)位置的改变可以采用同样的方法证明。用反证法证明时，关键是证明反例不成立，由此推出原方案是最优的。第十三页，共38页。问题(wèntí)推广：排队打水问题(wèntí)有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…….tn为整数且各不相等，应如何安排他们的打水顺序(shùnxù)才能使他们总共花费的时间最少？第十四页，共38页。例题(lìtí)3：打包某工厂生产出的产品都要被打包放入正四棱柱的盒子内，所有盒子的高度为h，但地面(dìmiàn)尺寸不同，可以为1x1、2x2、3x3、4x4、5x5、6x6。如下图所示。这些(zhèxiē)盒子将被放入高度为h，地面尺寸为6x6的箱子中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好算法，能使箱子的数量降到最低，这将给工厂节省不少的资金。请你编写一个程序。第十五页，共38页。分析(fēnxī)第十六页，共38页。分析(fēnxī)第十七页，共38页。例题(lìtí)4:均分纸牌（NOIP2002）有N堆纸牌，编号分别为1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若于张纸牌，然后移动。

移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如N=4，4堆纸牌数分别为：①9②8③17④6

移动3次可达到(dádào)目的：从③取4张牌放到④(981310)->从③取3张牌放到②(9111010)->从②取1张牌放到①(10101010）。第十八页，共38页。分析(fēnxī)：【试题分析】我们要使移动次数最少，就是要把浪费(làngfèi)降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费(làngfèi)，因为我们可以把它们合并为一次或零次。【思路点拨】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆,步数是一样的。注意最左边的0和最右边的0不能算在内，如0,0,1,-3,4,0,-1,0,0第十九页，共38页。扩展(kuòzhǎn)1：若题目中的纸牌排成一个环状，应如何处理(chǔlǐ)呢？其中n<=1000。第二十页，共38页。扩展(kuòzhǎn)2：有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得(huòdé)均等糖果的最小代价。【数据规模】对于30%的数据n<=1000；对于100%的数据n<=1000000第二十一页，共38页。贪心的经典(jīngdiǎn)应用（一）、三个区间上的问题1、选择不相交(xiāngjiāo)区间问题2、区间选点问题3、区间覆盖问题（二）、两个调度问题1、流水作业调度问题2、带限期和罚款的单位时间任务调度（三）Huffman编码（四）最优合并问题第二十二页，共38页。1、选择不相交区间(qūjiān)问题给定n个开区间(ai,bi)，选择尽量(jǐnliàng)多个区间，使得这些区间两两没有公共点。【算法实现】首先按照b1<=b2<=…<=bn的顺序排序，依次(yīcì)考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

贪心策略：取第一个区间；

【正确性】：如果不选b1，假设第一个选择的是bi，则如果bi和b1不交叉则多选一个b1更划算；如果交叉则把bi换成b1不影响后续选择。第二十三页，共38页。例题(lìtí)5：活动安排设有n个活动的集合E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择(xuǎnzé)了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当fi<=sj或fj>=si时，活动i与活动j相容。选择(xuǎnzé)出由互相兼容的活动组成的最大集合。第二十四页，共38页。2、区间(qūjiān)选点问题给定(ɡěidìnɡ)n个闭区间[ai,bi]，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。【算法】：首先按照b1<=b2<=…<=bn排序。每次标记当前(dāngqián)区间的右端点X，并右移当前(dāngqián)区间指针，直到当前(dāngqián)区间不包含X，再重复上述操作。

贪心策略：取最后一个。第二十五页，共38页。例题(lìtí)6：种树（NOIP模拟试题）一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区(dìqū)被分割成块，并被编号为1..n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b<=e,居民必须保证在指定地区(dìqū)不能种多于地区(dìqū)被分割成块数的树，即要求t<=e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。第二十六页，共38页。3、区间覆盖(fùgài)问题给n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定(zhǐdìng)线段[s,t]。本题的突破口仍然是区间包含(bāohán)和排序扫描，不过先要进行一次预处理。每个区间在[s,t]外的部分都应该预先被切掉，因为它们的存在是毫无意义的。在预处理后，在相互包含(bāohán)的情况下，小区间显然不应该考虑。第二十七页，共38页。把各区间按照a从小到大排序，若a相同，则b从大到小排序（自动处理掉区间包含）。注意：若区间1的起点大于s，则无解（因为其他区间的起点更大，不可能覆盖到s点），否则选择起点在s的最长区间[ai,bi]后，新的起点应该设置为bi，并且忽略所有区间在bi之前的部分，就像预处理一样(yīyàng)。虽然贪心策略比上题复杂，但是仍然只需要一次扫描，如下图，s为当前有效起点（此前部分已被覆盖），则应该选择区间2。贪心思想：在某个时刻s，找一个(yīɡè)满足a[i]>=s的b[i]的最大值即可。第二十八页，共38页。例题(lìtí)7：区间（SDOI2005）现给定n个闭区间[ai,bi]，1<=i<=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是(jiùshì)在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a,b]和[c,d]是按照升序排列的，那么我们有a<b<=c<=d。

任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。第二十九页，共38页。练习试题(shìtí)：喷水装置有一块草坪，长为L，宽为w；在它的中心线上装有n个点状的喷水装置，效果是让以它为中心半径为ri的圆被润湿(rùnshī)，选择尽量少的喷水装置把整个草坪全部润湿(rùnshī)。第三十页，共38页。1、流水作业调度(diàodù)问题第三十一页，共38页。分析(fēnxī)第三十二页，共38页。2、带限期(xiànqī)和罚款的单位时间任务调度第三十三页，共38页。旅行家的预算(yùsuàn)一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位(dānwèi)）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“NoSolution”。样例：InputD1=275.6 C=11.9 D2=27.4 P=2.8 N=2油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2Output26.95（该数据表示最小费用）第三十四页，共38页。分析(fēnxī)：需要考虑如下问题：出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？汽车行程到第几站开始加油，加多少油？可以(kěyǐ)看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以(kěy