贪心算法 1428：数列分段 1427：数列极差 1432：糖果传递 导弹拦截 p1020 洛谷 P1106 删数问题
贪心算法
贪心算法其实就是来求解最优化问题的一种常用算法
一、贪心算法
贪心算法是从问题的初始状态出发,通过若干次的贪心选择而得到的最优值(或较优值)的一种求解问题策略,即贪心策略。
换句话说,贪心策略是一种在每次决策时采取当前意义下最优策略的算法,做出的选择只是在某种约束条件下的局部最优解或较优解,并不一定是全局的最优解或较优解。不过,某些特定的问题是可以利用贪心算法求得其最优解或较优解的。
二、贪心算法的特点
1.贪心选择
所谓贪心选择是指应用同一规则,将原问题变为一个相似的但规模更小的子问题,面后的每一步都是当前看似最佳的选择,且这种选择只依赖于已做出的选择,不依赖于未做出的选择
2.最优子结构
执行算法时,每一次得到的结果虽然都是当前问题的最优解( 即局部最优解 ),但只有满足全局最优解包含局部最优解时,才能保证最终得到的结果是最优解
也就是可以由局部最优推出全局最优
三、几个简单的贪心实例
1.最优装载问题
给n个物体,第i个物体重量为w,选择尽量多的物体,使得总重量不超过C
【思路点拨】
由于只关心物体的数量,所以装重的没有装轻的划算,只需把所有物体按重量从小到大排序,依次选择每个物体,直到装不下为止。
贪心策略:先装最轻的。
2.部分背包问题
有n个物体,第i个物体的重量为w,价值为,在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分,价值和重量按比例计算
【思路点拨】
优先选出价值与重量的比值最大的,直到重量和正好为C.
贪心策略:先选出性价比高的
3.乘船问题
有n个人,第i个人重量为w,每艘船的载重量均为C,最多可乘两个人,求用最少的船装载所有人的方案
【思路点拨】
考虑最轻的人i,他应该和谁一起乘呢?如果每个人都不能和他一起乘,则只能每人乘一艘船,否则,他应该选择能和他一起乘的人中最重的一个人j。这样的选择只是让“眼前”的浪费最少
贪心策略:最轻的人和最重的人配对
四、贪心算法的经典应用
1.选择不相交区间问题
给定n个开区间( ai ,bi ),选择尽量多个区间,使得这些区间两两没有公共点
【思路点拨】
首先,按照结束时间从小到大排序,依次考虑各个活动,如果没有和已经选择的活动冲突,就选;否则就不选
要求对后面影响小
【例题】 1422：【例题1】活动安排
给定n个闭区间[a,b],在数轴上选尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)
【思路点拨】
首先按照区间的结束位置从小到大排序。然后从区间1到区间n进行选择:对于当前区间,若集合中的数不能覆盖它,则将区间末尾的数加入集合
贪心策略:取最后一个。
3.区间覆盖问题
给n个闭区间[a,b],选择尽量少的区间覆盖一条指定的线段区间[s,t]
【思路点拨】
将所有的区间按左端点从小到大排序,依次处理每个区间。每次选择覆盖点s的区间中右端点坐标最大的一个,并将s更新为该区间的右端点坐标,直到选择的区间已包含了t为止
贪心策略:在某个时刻的s,找一个满足a[i]≤s的b[i] 最大值即可
4.流水作业调度问题
有n个作业要在两台机器M1和M2组成的流水线上完成加工。每个作业i都必须先花时间ai在M1上加工,然后花时间bi在M2上加工
确定n个作业的加工顺序,使得从作业1在机器M1上加工开始到作业n在机器M2上加工为止所用的总时间最短。
【思路点拨】
直观上,最优调度一定让M1没有空闲,M2的空闲时间尽量短。
Johnson算法;
设N1为a<b的作业集合,N2为a≥b的作业集合,将N1的作业按a非减序排序,N2中的作业按照b非增序排序,则N1作业接N2作业构成最优顺序。
算法的程序易于实现,时间复杂度为O( nlogn)
【例题】 1425：【例题4】加工生产调度
5.带限期和罚款的单位时间任务调度
有n个任务,每个任务都需要1个时间单位执行,任务 i 的截止时间d(1≤di≤n)表示要求任务i在时间di 结束时必须完成,误时惩罚wi表示若任务i未在时间di结束之前完成,将导致wi的罚款
确定所有任务的执行顺序,使得惩罚最少
【思路点拨】
要使罚款最少,我们显然应尽量完成w值较大的任务
此时,我们可以将任务按w从大到小进行排序,然后按照排好的顺序依次对任务进行安排。
安排的规则为:使处理任务i的时间既在d[i]之内,又尽量靠后;如果i之内的时间都已经排满,就放弃处理此项任务。
【实现方法】
①先按照罚款数额从大到小快排
②顺序处理每个任务,若能安排,则找一个最晚时间;否则放在最后的空位上