贪心算法其实就是来求解最优化问题的一种常用算法
贪心算法是从问题的初始状态出发, 通过若干次的贪心选择而得到的最优值 (或较优值) 的一种求解问题策略, 即贪心策略.
换句话说, 贪心策略是一种在每次决策时采取当前意义下最优策略的算法, 做出的选择只是在某种约束条件下的局部最优解或较优解, 并不一定是全局的最优解或较优解. 不过, 某些特定的问题是可以利用贪心算法求得其最优解或较优解的.
二, 贪心算法的特点
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] 活动安排
2. 区间选点问题
给定 n 个闭区间[a,b], 在数轴上选尽量少的点, 使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)
[思路点拨]
首先按照区间的结束位置从小到大排序. 然后从区间 1 到区间 n 进行选择: 对于当前区间, 若集合中的数不能覆盖它, 则将区间末尾的数加入集合
贪心策略: 取最后一个.
[例题] 1423:[例题 2] 种树
3. 区间覆盖问题
给 n 个闭区间[a,b], 选择尽量少的区间覆盖一条指定的线段区间[s,t]
[思路点拨]
将所有的区间按左端点从小到大排序, 依次处理每个区间. 每次选择覆盖点 s 的区间中右端点坐标最大的一个, 并将 s 更新为该区间的右端点坐标, 直到选择的区间已包含了 t 为止
贪心策略: 在某个时刻的 s, 找一个满足 a[i]≤s 的 b[i] 最大值即可
[例题] 1424:[例题 3] 喷水装置
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 之内的时间都已经排满, 就放弃处理此项任务.
[实现方法]
1先按照罚款数额从大到小快排
2顺序处理每个任务, 若能安排, 则找一个最晚时间; 否则放在最后的空位上
[例题] 1430: 家庭作业
五, 贪心练习题
1428: 数列分段
1427: 数列极差
导弹拦截 p1020
洛谷 P1106 删数问题
贪心算法
来源: http://www.bubuko.com/infodetail-3086319.html