37.贪心算法

贪心算法

贪心算法关键是多联系,记住 其核心是 保证 每一步做出当前 性价比最高的选择

解题步骤

第一步, 一组数据 限制值 期望值 三个关键字

第二步, 运用贪心思想, 每次都选择 当次情况下 同等限制资源对期望贡献最高的数据

第三步, 举几个例子试下 贪心思想是否最优解

当前面的选择 影响 后面的选择时, 贪心算法并不是全局最优解,不能用.

例如,多条路径多分叉的最短路径,可能第一条路选了最短的,

但由于选了这条路,导致这条路后面的每一步都比其他路糟糕.

贪心算法 分治算法 回溯算法 动态规划 四个算法思想

greedy algorithm

适用场景: 一组数据,定义了 限制值 和 期望值, 在满足限制值的情况下,期望值最大

典型应用: 霍夫曼编码(Huffman Coding)/Prim 和 Kruskal 最小生成树算法/Dijkstra 单源最短路径算法

(1)分糖果

m个糖果 n个孩子, m < n,所以糖果只能分给一部分孩子.

每个糖果大小不等(s1,s2,s3…sm),

每个孩子对糖果大小的需求也不等(g1,g2,g3…gn),

只有 孩子得到的糖果大小 s > g 需求大小 时才能满足,

如何分配 满足最多数量 的孩子?

限制条件: 加起来m个糖果, 期望值: 满足数量最多的孩子,

性价比: 需求最小的孩子 恰好满足需求的糖果

分发饼干(LeetCode 455)

var findContentChildren = function(g, s) {
    let gp = 0,sp = 0
    g.sort((l,r) => l - r)
    s.sort((l,r) => l - r)
    while(gp < g.length && sp < s.length) {
        if(g[gp] <= s[sp]) {
            gp ++
        }
        sp ++
    }
    return gp
};

(2)钱币找零

有 c1 c2 c5 c10 c20 c50 c100 面额的纸币,用来付 k 元,

如何用最少张钱币来支付k元?

限制条件: 加起来为k元, 期望值: 使用的钱币最少

性价比: 面额越大的钱币

柠檬水找零(leetcode 860)

(3)区间覆盖

有n个区间,例如:[6,8] [2,4] [3,5] [1,5] [5,9] [8,10]

从这n个区间中找出一部分区间,这部分区间 两两不相交(端点不算),

最多选出多少个区间呢?

限制条件: 区间最左端到最右端[1,10], 期望值: 选出的区间最多

性价比: 自身区间越短的区间

解法:找出区间最左端与最右端例如[1,10],

每次选择 左端点与之前不重合 右端点尽量小.(还有一些额外情况需要考虑)

其反例,找重复区间也是贪心算法,如下面这题

用最少数量的箭引爆气球(leetcode 452)

(4)移除k个数组

非负整数a,移除其中k个数字,让剩下的数字值最小,移除哪k个数字?

限制条件: 共移除k个数字, 期望值: 移除完后的结果最小

性价比: 高位且大于下一位的数字(靠左却大于右侧数字 的数字)

移掉K位数字(leetcode 402)

(5)等待时间最短

n个人等待服务,每个人需要的服务时间长度不同,

如何安排顺序,使n个人总等待时间最短?

限制条件: 顺序(?我也不确定), 期望值: 总等待时间最短

性价比: 服务时间短的人

其他

贪心算法的使用场景比较有限,这种算法思想更多的是 指导设计基础算法.

比如: 最小生成树算法,单源最短路径算法.

贪心算法的 关键 是多练习, 难点 是将问题抽象成贪心算法模型,

贪心算法的编码一般很简单.

贪心算法的正确性是显而易见的,但证明需要严谨复杂的数学论证.