算法-贪心算法详解

ゞ浴缸里的玫瑰 2022-11-14 10:27 179阅读 0赞

**目录**

概述

引入

钞票支付问题

解答

最优子结构

区间问题

leetcode 435 无重叠区间

解答

问题转换

leetcode 55 跳跃游戏

解答

题目

--------------------

# 概述 #

顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是**局部最优**的，从而使最后得到的结果是全局最优的。

# 引入 #

## 钞票支付问题 ##

有1元、5元、10元、20元、100元的钞票**无穷多张**。现使用这些钞票支付X元，**最少**需要多少张?  
例如，X=628

## 解答 ##

按照常识，我们先使用大额的进行支付。

from typing import List
    
    
    def getMinNum(moneys: List[int], X: int) -> int:
        moneys.sort(reverse=True)
        i, ans = 0, 0
        while X != 0:
            number = X // moneys[i]
            X -= moneys[i] * number
            print(moneys[i], number)
            ans += number
            i += 1
        return ans
    
    
    if __name__ == '__main__':
        moneys = [1, 2, 5, 10, 20, 100]
        X = 628
        print(getMinNum(moneys, X))

> 100 6  
> 20 1  
> 10 0  
> 5 1  
> 2 1  
> 1 1  
> 10

虽然结果是对的，但是我们并没有给出证明。这里也不用数学公式证明了，简单一句话就是**大的钞票可以换成小的钞票**，若使用小的钞票，那么会更多，不符合题目要求。其次，最优解包含子问题的最优解，628的最优解去除1就是627的最优解。

思考一个问题，如果钞票面值添加7呢？

相信读者看到了，若还是贪心的话，14的结果就不对了，因为14的最优解为7\*2，2张即可。

# 最优子结构 #

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。

X=14时，选7+7比选10+2+2要好。或者说，X=14时的第一个选择7，不是子问题X=13时的第一个选择10。这样先选最大的这种贪心策略就不对了。

以上，就说明了只有**通过子问题的最优解能推导出问题的最优解**的情况下才能使用贪心算法。

接下来看几个典型问题。

# 区间问题 #

## leetcode 435 无重叠区间 ##

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。  
    区间 \[1,2\] 和 \[2,3\] 的边界相互“接触”，但没有相互重叠。

示例 1:

> 输入: \[ \[1,2\], \[2,3\], \[3,4\], \[1,3\] \]
> 
> 输出: 1
> 
> 解释: 移除 \[1,3\] 后，剩下的区间没有重叠。

## 解答 ##

如果已经确定了一个区间，如何确定另一附近区间呢？由于题目要要移除区间的的最小数量，我们应该**选择延展最少的（贪心）**，这样覆盖的少。例如，我们确定了从小到大，选区了第一个区间，而有一区间的右端点比较大，若选择它，那么很多右端点小的就会和这一区间重复，导致去除了很多重复区间。因此，这里按照区间右端点从小到大排序，选择第一个区间开始，依次向后判断是否重叠，重叠则去除。

class Solution:
        def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
            intervals.sort(key=lambda x: x[1])
            print(intervals)
    
            # 返回是否重叠
            def isOver(a, b):
                if b[0] < a[1]:
                    return True
                return False
    
            start, ans = intervals[0], 0
            for cur in intervals[1:]:
                if isOver(start, cur):
                    ans += 1
                else:
                    start = cur
            return ans

当然，你如果选择最右边的开始也是一样的。

# 问题转换 #

## leetcode 55 跳跃游戏 ##

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

> 输入：nums = \[2,3,1,1,4\]  
> 输出：true  
> 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

> 输入：nums = \[3,2,1,0,4\]  
> 输出：false  
> 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

## 解答 ##

第一时间想到的可能是每次**选择最远的跳**，这样可以跳的“更远”，从而达到最后。其实这样是不对的，可能**你跳的“更远”的下一跳反而比其他选择的下一跳近**，所以我们并不是选择跳的最远的，而是选择**在可跳的范围内最终能跳的最远的。**

这就是对局部最优的理解，你没有沿着你的选择跳到最后，你并不知道是不是局部最优。因此，我们维护一个当前能跳的最远位置，将所有选择的下一跳计算出来并持续更新最远位置。

class Solution:
        def canJump(self,nums):
            n = len(nums)
            max_pos = 0                               # 当前最远位置
            for pos, jump in enumerate(nums):         # poi为当前位置，jump是当前位置的跳数
                if max_pos>=pos and pos+jump>max_pos: # 如果当前位置能到达，并且 当前位置+跳数>最远位置，
                    max_pos = pos+jump                # 更新最远能到达位置
                # 提前结束
                if max_pos >= n - 1:
                    return True
                if max_pos < pos:
                    return False
            return True

当然，我们可以提前结束，让我们的程序性能更好。

大家可以练练相关题目，巩固一下。

# 题目 #

[leetcode 435 无重叠区间][leetcode 435]

[leetcode 455 分发糖果][leetcode 455]

[leetcode 376 摆动序列][leetcode 376]

[leetcode 402 移掉K位数字][leetcode 402 _K]

[leetcode 55 跳跃游戏][leetcode 55]

[leetcode 435]: https://leetcode-cn.com/problems/non-overlapping-intervals/
[leetcode 455]: https://leetcode-cn.com/problems/assign-cookies/
[leetcode 376]: https://leetcode-cn.com/problems/wiggle-subsequence/
[leetcode 402 _K]: https://leetcode-cn.com/problems/remove-k-digits/
[leetcode 55]: https://leetcode-cn.com/problems/jump-game/