贪心算法(1)

贪心算法贪心方法的基本思想•贪心是一种解题策略，也是一种解题思想•使用贪心方法需要注意局部最优与全局最优的关系，选择当前状态的局部最优并不一定能推导出问题的全局最优•利用贪心策略解题，需要解决两个问题：–该题是否适合于用贪心策略求解–如何选择贪心标准，以得到问题的最优解•【引例】在一个N×M的方格阵中，每一格子赋予一个数（即为权），规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。•我们以2×3的矩阵为例：若按贪心策略求解，所得路径为：1→3→4→6；若按动态规划求解，所得路径为：1→2→10→6。贪心法的特点•1.贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。•2.最优子结构性质：算法中每一次都取得了最优解(即局部最优解)，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。•但并不是所有具有最优子结构的问题都可以用贪心策略求解。因为贪心往往是盲目的，需要使用更理性的方法——动态规划（例如“0-1背包问题”与“部分背包问题”）【问题1】部分背包问题•给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第i种食品的最多拥有Wi公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。【分析】因为每一个物品都可以分割成单位块，单位块的利益越大，显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：先将单位块收益按从大到小进行排列，然后用循环从单位块收益最大的取起，直到不能取为止便得到了最优解。【问题2】0/1背包问题•给定一个最大载重量为M的卡车和N种动物。已知第i种动物的重量为Wi，其最大价值为Vi，设定M，Wi，Vi均为整数，编程确定一个装货方案，使得装入卡车中的所有动物总价值最大。【分析】按贪心法：每次选价格最大的装载。很明显有反例：设N=3,卡车最大载重量是100,三种动物A、B、C的重量分别是40,50,70,其对应的总价值分别是80、100、150。贪心策略与其他算法的区别•1.贪心与递推：与递推不同的是，贪心法中推进的每一步不是依据某一固定的递推式，而是当前看似最佳的贪心决策，不断的将问题归纳为更加小的相似的子问题。所以归纳、分析、选择正确合适的贪心策略，是正确解决贪心问题的关键。•2.贪心与动态规划：与动态规划不同的是，贪心是鼠目寸光；动态规划是统揽全局。几个简单的贪心例子贪心策略例题1：删数问题•键盘输入一个高精度的正整数n（n=240位）,去掉其中任意s个数字后剩下的数字按照原来的次序将组成一个新的正整数。编程对给定的n和s,寻求一种方案,使得剩下组成的新数最小。•【样例输入】178543182914•【样例输出】13分析•由于正整数n的有效位数最大可达240位，所以可以采用字符串类型来存储n。那么，应如何来确定该删除哪s位呢？是不是只要删掉最大的s个数字就可以了呢？•为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。例题2：排队问题•在一个食堂，有n个人排队买饭，每个人买饭需要的时间为Ti，请你找出一种排列次序，是每个人买饭的时间总和最小。•【思路点拨】由题意可知，本题可以采用的贪心策略为：将n个人排队买饭的时间从小到大排序，再依次累加每人的买饭时间，即可得到最小的总和。由样例可知，排好序后的数据为(1,3,5,7,9,11)，每个人的买饭时间如下：•T1=1•T2=T1+t2=1+3=4•T3=T2+t3=4+5=9•T4=T3+t4=9+7=16•T5=T4+t5=16+9=25•T6=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次，其他一样。由此，两者相比较，可知有序的序列能得到最优的方案。对于其他位置的改变可以采用同样的方法证明。用反证法证明时，关键是证明反例不成立，由此推出原方案是最优的。问题推广：排队打水问题•有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2…….tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？例题3：打包•某工厂生产出的产品都要被打包放入正四棱柱的盒子内，所有盒子的高度为h，但地面尺寸不同，可以为1x1、2x2、3x3、4x4、5x5、6x6。如下图所示。这些盒子将被放入高度为h，地面尺寸为6x6的箱子中。为了降低运送成本，工厂希望尽量减少箱子的数量。如果有一个好算法，能使箱子的数量降到最低，这将给工厂节省不少的资金。请你编写一个程序。分析分析例题4:均分纸牌（NOIP2002）有N堆纸牌，编号分别为1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若于张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如N=4，4堆纸牌数分别为：①9②8③17④6移动3次可达到目的：从③取4张牌放到④(981310)-从③取3张牌放到②(9111010)-从②取1张牌放到①(10101010）。分析：•【试题分析】我们要使移动次数最少，就是要把浪费降至零。通过对具体情况的分析，可以看出在某相邻的两堆之间移动两次或两次以上，是一种浪费，因为我们可以把它们合并为一次或零次。•【思路点拨】如果你想到把每堆牌的张数减去平均张数，题目就变成移动正数，加到负数中，使大家都变成0，那就意味着成功了一半！•从第i堆移动-m张牌到第i+1堆，等价于从第i+1堆移动m张牌到第i堆,步数是一样的。•注意最左边的0和最右边的0不能算在内，如0,0,1,-3,4,0,-1,0,0扩展1：•若题目中的纸牌排成一个环状，应如何处理呢？•其中n=1000。扩展2：•有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。•【数据规模】对于30%的数据n=1000；对于100%的数据n=1000000贪心的经典应用（一）、三个区间上的问题1、选择不相交区间问题2、区间选点问题3、区间覆盖问题（二）、两个调度问题1、流水作业调度问题2、带限期和罚款的单位时间任务调度（三）Huffman编码（四）最优合并问题1、选择不相交区间问题•给定n个开区间(ai,bi)，选择尽量多个区间，使得这些区间两两没有公共点。【算法实现】首先按照b1=b2=…=bn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。贪心策略：取第一个区间；【正确性】：如果不选b1，假设第一个选择的是bi，则如果bi和b1不交叉则多选一个b1更划算；如果交叉则把bi换成b1不影响后续选择。例题5：活动安排•设有n个活动的集合E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当fi=sj或fj=si时，活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。2、区间选点问题•给定n个闭区间[ai,bi]，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。【算法】：首先按照b1=b2=…=bn排序。每次标记当前区间的右端点X，并右移当前区间指针，直到当前区间不包含X，再重复上述操作。贪心策略：取最后一个。例题6：种树（NOIP模拟试题）•一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1..n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b=e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t=e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。3、区间覆盖问题•给n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[s,t]。•本题的突破口仍然是区间包含和排序扫描，不过先要进行一次预处理。每个区间在[s,t]外的部分都应该预先被切掉，因为它们的存在是毫无意义的。在预处理后，在相互包含的情况下，小区间显然不应该考虑。•把各区间按照a从小到大排序，若a相同，则b从大到小排序（自动处理掉区间包含）。注意：若区间1的起点大于s，则无解（因为其他区间的起点更大，不可能覆盖到s点），否则选择起点在s的最长区间[ai,bi]后，新的起点应该设置为bi，并且忽略所有区间在bi之前的部分，就像预处理一样。虽然贪心策略比上题复杂，但是仍然只需要一次扫描，如下图，s为当前有效起点（此前部分已被覆盖），则应该选择区间2。贪心思想：在某个时刻s，找一个满足a[i]=s的b[i]的最大值即可。例题7：区间（SDOI2005）•现给定n个闭区间[ai,bi]，1=i=n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a,b]和[c,d]是按照升序排列的，那么我们有ab=c=d。任务：读入这些区间，计算满足给定条件的不相交闭区间，并把这些区间按照升序输出。练习试题：喷水装置•有一块草坪，长为L，宽为w；在它的中心线上装有n个点状的喷水装置，效果是让以它为中心半径为ri的圆被润湿，选择尽量少的喷水装置把整个草坪全部润湿。1、流水作业调度问题分析2、带限期和罚款的单位时间任务调度旅行家的预算•一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。•计算结果四舍五入至小数点后两位。•如果无法到达目的地，则输出“NoSolution”。•样例：•Input•D1=275.6C=11.9D2=27.4P=2.8N=2•油站号I离出发点的距离Di每升汽油价格Pi1102.02.92220.02.2•Output•26.95（该数据表示最小费用）分析：•需要考虑如下问题：•出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？•汽车行程到第几站开始加油，加多少油？•可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：•对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。•对于第一种情况，则