深入了解贪心算法定义及基本步骤

小白2021-08-18 15:23

如果你认为贪心算法只是每次都选择最优方案的算法,那你只了解到一半,有一个重要的限制条件是针对当前状态。也就是说只选当前状态的最优解,不从整体考虑是否最优,可以理解为某种程度上的“局部最优解”,即具备无后效性。

贪心算法其实是最常用的算法,代码实现也很短。它的基本步骤为:

(1)建立对问题精确描述的数学模型,包括定义最优解的模型;

(2)将问题分解为一系列子问题,同时定义子问题的最优解结构;

(3)应用贪心原则确定每个子问题的局部最优解,并根据最优解的模型,用子问题的局部最优解堆叠出全局最优解。

以下面这个会议问题为例,有些项目需要占用一个会议室进行演示,会议室不能同时容纳两个演示。给你所有的项目和每个项目的开始时间和结束时间,你会安排演讲的日程,要求会议室有最多的演讲。回到这个最讲道的会议。

贪婪策略A:项目越早开始,就越早安排。——无法获得全局最优解。

贪心算法

贪心策略B:项目工期越短,优先安排。——无法获得全局最优解。

贪心算法

贪婪策略C:先安排提前结束的项目。——可以得到全局最优解。

public class Solution {
        
    static class Program {
        // 项目开始时间
        public int begin;
        // 项目结束时间
        public int end;
        public Program(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }
    }

    // 定义Program比较器,按照Program的结束时间来比较
    static class ProgramComparator implements Comparator<Program> {
        @Override
        public int compare(Program program1, Program program2) {
            return program1.end - program2.end;
        }
    }

    public int arrangeProgram(Program[] programs, int currentTime) {
        if (programs == null || programs.length == 0) {
            return 0;
        }
        // 可以安排项目的场数
        int number = 0;
        // 将Program数组按照结束时间早晚来排序,结束早的排前面
        Arrays.sort(programs, new ProgramComparator());
        for (int i = 0; i < programs.length; i ++) {
            // 如果当前时间还没到会议开始时间,安排会议
            if (currentTime < programs[i].begin) {
                number ++;
            }
            // 当前时间来到会议结束
            currentTime = programs[i].end;
        }
        return number;
    }
}

以上就是“深入了解贪心算法定义及基本步骤”一文,想了解更多相关内容,推荐大家一个高质量公开课,《详细解析贪心算法》,点击下方图片立即免费领取。

贪心算法

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用。如涉及版权问题,请联系本站管理员予以更改或删除。
有用
分享