网站开发感受,网站建设困难,wordpress模板游戏推广,秀洲区住房和城乡建设局网站贪心选择是指应用同一规则#xff0c;将原问题变为一个相似但是规模更小的问题#xff0c;而后的每一步都是当前看起来最佳的选择#xff0c;且这种选择只依赖于已做出的选择#xff0c;不依赖于未作出的选择。 贪心算法说起来容易#xff0c;操作起来却经常有点玄学。将原问题变为一个相似但是规模更小的问题而后的每一步都是当前看起来最佳的选择且这种选择只依赖于已做出的选择不依赖于未作出的选择。 贪心算法说起来容易操作起来却经常有点玄学。我怎么想的到 在这里整理一些常见的贪心题目 选择不相交区间问题 这种问题一般具体题目大概就是时间安排场地安排之类有一个量不能被重复使用。解决这种问题的方法为按照对这个量使用的截至时间进行排序然后进行一次遍历如果下一事件开始比这一事件开始迟就将这个事件考虑在内。 证明如果下一事件的开始比这一事件迟却没有考虑则考虑下下一事件若开始时间比下一时间结束早那么将这两个事件哪个算上都无所谓若开始时间比下一事件迟则少考虑了一个所以上述贪心策略是合理的 注意在开始和结束的判断上能否相等需要注意 区间选点问题 同样的对区间按照末尾进行排序对这种区间问题一般考虑排序要不然乱糟糟的不可能找到规律 选择点的规则为尽量选择在区间末尾 因为区间与区间相交肯定在前一个区间的末尾相交所以如果尽量把点放在那里的话就能尽可能让下一个区间用到。 可以考虑用一个bool型数组表示点如果选择就进行标记即可 如果题目要求在区间内标记多个点那么同样还是尽量在区间的末尾放点先在这个区间内看一下是否需要再放如果需要从后往前放 区间覆盖问题 给定一定的区间选择尽量少的区间覆盖一条指定线段区间 还是得对区间进行排序不同的在于是对区间的左端点进行排序依次处理每个区间每次选择覆盖s的区间中右端点最大的一个并将线段的左端点更新为区间的右端点直到选择的区间包含线段的右端点为止。
