贪心算法, 它是一种需要做到在每一个步骤的选择当中, 都作出在当前时候看来是最优的选择的算法实现方式, 通过这种做去法最终希望获得全局最优的那种算法实现。它在每个步里面都会选择好那个最厉害的局部解决法子, 一般被拿出用来搞定那些优化问题。贪心算法实现的主要关键之处, 就在于如何选择一个属于局部最优解的策略。如下文所呈现的那样, 这一种策略本身需要符合下面这两个具体的条件要求。使用贪心算法来解决的一个最为经典的例子就是活动选择问题, 接下来我们就看看如何通过这种方法来解决它。活动选择问题关于活动选择问题, 可以将其简化理解为这样一番情形。现在呢, 是假设已经给定了一组活动的情况存在, 并且每一个活动, 它都是有一个开始时间以及一个结束时间的存在的。而要求的是需要在同一时间内这个限制条件成立的情况下一个人他只能去参加活动这其中的一个一个活动。那么最终要解决的一个核心问题就是, 需要去找出数量是最多的那些互不重叠的活动出来的这样一个结果。根据贪心算法的具体实施思路来开展我们的工作, 我们可以选用下面所提到的这种策略来进行操作。就是每一次都在众多活动当中去做出选择, 而这个选择标准是挑选出那个结束时间最早的环节去优先处理, 这样做的主要意图在于为后面还需要参与进来的其他各种各样的活动项目争取和腾出尽可能充足的剩余可用时间空间出来。代码实现的方式, 如我们所见所示那般情况。def activity_selection(activities):# 按结束时间排序activities.sort(keylambda x: x[1])# 初始化选中的活动列表selected_activities []# 上一个活动的结束时间last_end_time 0for activity in activities:# 如果活动的开始时间大于等于上一个活动的结束时间if activity[0] last_end_time:# 选择这个活动selected_activities.append(activity)# 更新上一个活动的结束时间last_end_time activity[1]return selected_activities# 测试activities [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]selected activity_selection(activities)print(选中的活动:, selected)代码执行结果选中的活动: [(1, 3), (3, 5), (5, 7), (8, 9)]在算法执行之初, 首先是利用活动的结束时间点作为依据, 将手头所有的活动做一个排序处理。紧接着是从排在首位的那个活动算起, 挨个儿地去查看每一个活动的状况, 看看它能不能被塞进已经选定好的一堆活动名单里头去。要是判断下来, 眼前这个活动它的开始时间比上一个已经被选中活动的结束时间来得早或者正好赶上, 也就是不小于那个时间点, 那就干脆把这个活动也给它选上。通过进行这样的操作, 就可以保证每一次所选择的活动都不会跟 已经选择过的活动出现重叠的情况, 同时也会最大限度地给之后的活动腾出更多的时间空间, 进而实现将数量最多的活动挑选出来的这个目标。总结前面, 我们向大家展示了怎样去实现一个贪心算法, 可是呢, 这里头还存在着一个问题, 那就是, 也不是说所有的什么问题都能够借由这个贪心算法去拿到那个最优解的, 所以在用到这个贪心算法的时候, 是有必要去证明一下自己所选的那个策略到底对不对的,得确保每一步所做的那个贪心的选择都是能获取到这个全局的最优解的。从上面的这种例子当中, 咱们也可以看出来, 贪心算法在处理某些优化问题的时候, 确实是有它的那种有效性的, 不过在那些实际的运用场景里边, 咱们是需要去把那些具体的问题结合起来看的, 需要去分析一下是不是满足了那个贪心选择性质, 还有那个最优子结构性质这两个方面的条件的, 然后才是根据这些情况来去决定要不要去使用贪心算法去处理那些问题的。
