python实现贪心算法

╰半夏微凉° 2022-11-12 12:59 124阅读 0赞

> 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。

**1. 贪心算法思想**  
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

**2.贪心算法的过程：**  
1．建立数学模型来描述问题  
2．把求解的问题分成若干个子问题  
3．对每一子问题求解，得到子问题的局部最优解  
4．把子问题的解局部最优解合成原来解问题的一个解

算法求解过程是首先从某一解向目标值出发，得到可行解的元素，然后合成所有解元素而得到一个可行解。

**3.贪心算法的不足**  
贪心算法的解题方式是从可选的第一个解开始逐步到达目标解，如果在寻解的过程中因某种条件限制而停止向前，就得到一个近似解，因此贪心算法存在以下不足：  
1）贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。  
2) 不适用于最值问题

**4.贪心选择的定义**

贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

**5.最优子结构的定义**

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题 。  
**6.贪心算法例题（均为leetcode题目）**

例1）给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。  
注意:  
num 的长度小于 1000 且 ≥ k。  
num 不会包含任何前导零。  
示例 1 :  
输入: num = “1432219”, k = 3  
输出: “1219”  
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

**解题思路：**  
贪心 + 单调栈  
对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，例如，对于 A=1axxxA = 1axxxA=1axxx，B=1bxxxB = 1bxxxB=1bxxx，如果 a>ba > ba>b 则 A>BA > BA>B。  
基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70_pic_center]  
给定一个数字序列，例如 425，如果要求我们只删除一个数字，那么从左到右，我们有 4、2 和 5 三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始，2 小于它的左邻居 4。假设我们保留数字 4，那么所有可能的组合都是以数字 4（即 42，45）开头的。相反，如果移掉 4，留下 2，我们得到的是以 2开头的组合（即 25），这明显小于任何留下数字 4 的组合。因此我们应该移掉数字 4。如果不移掉数字 4，则之后无论移掉什么数字，都不会得到最小数。

基于此，我们可以每次对整个数字序列执行一次这个策略；删去一个字符后，剩下的 n−1 长度的数字序列就形成了新的子问题，可以继续使用同样的策略，直至删除 k 次。  
我们可以用一个栈维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过 k 次个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除次数之前，栈中的序列从栈底到栈顶单调不降。

因此，对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到：  
**1.栈为空  
2.或者新的栈顶元素不大于当前数字  
3.或者我们已经删除了 k 位数字**  
上述步骤结束后我们还需要针对一些情况做额外的处理：

1.  如果我们删除了 m 个数字且 m<k，这种情况下我们需要从序列尾部删除额外的 k−m 个数字。  
    2.如果最终的数字序列存在前导零，我们要删去前导零。  
    3. 如果最终数字序列为空，我们应该返回 0。

最终，从栈底到栈顶的答案序列即为最小数。

def removeKdigits(num, k):
        #辅助栈
        numStack = []
        # 构建单调递增的数字串
        for digit in num:
            while k and numStack and numStack[-1] > digit:
                numStack.pop()
                k -= 1
    
            numStack.append(digit)
    
        # 如果 K > 0，删除末尾的 K 个字符
        finalStack = numStack[:-k] if k else numStack
    
        # 抹去前导零
        return "".join(finalStack).lstrip('0') or "0"

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/a7c46166342b415e8273dafbcbeb5a02.png