贪心法(1): 贪心算法入门
最新回答
狗屎味的小仙女
2026-04-26 22:14:11
贪心算法是指从问题的初始状态出发，通过多次的贪心选择，最终得到整个问题的最优解。它是一种最接近人们日常思维的算法。由于贪心算法比较简单直观，因此在最优化问题中有着十分广泛的应用。
贪心策略通常只考虑当前局部最优策略，最终得到全局的最优解。这是由于问题本身包含特定的性质，保证了当前局部的贪心策略可以获得最优解。由于贪心的局部性，因此贪心算法往往比其他算法更加简单，易于实现。与此同时，一些直观的贪心策略虽然在局部是最优的，但是能否保证得到全局的最优解是贪心问题的关键。
在实际问题中，贪心策略通常会将问题切分成不同的阶段，并通过一系列的贪心选择来得到一个问题的最优解，而每次的选择都是当前状态的一种最优选择，即贪心选择，然后问题被转化成一个相同形式的子问题。为了最终可以得到的最优解，贪心问题需要满足最优子结构和贪心选择的性质。最优子结构是指，一个问题的最优解包含其子问题的最优解；而贪心选择性质是指所求问题的整体最优解可以通过一系列的局部最优选择来达到，这两点就保证了贪心策略可以达到最优解。
对于一个具体的贪心问题，在确定贪心选择之后，可以将问题转化为规模更小的问题，同时也需要证明贪心策略的正确性，常用的方法包括数学归纳法等，通过对算法步骤或者问题规模的划分，叙述一个正确的命题，然后对于不同阶段进行归纳，证明每一步贪心选择的正确性，从而证明整个贪心策略的正确性。
在实际的贪心算法的设计过程中，首先要将问题转化为多步判断，整个序列对应问题本身的最优解，而子序列对应子问题的解；然后通过设计贪心选择，将原问题规约成子问题的解，在这里，如何设计贪心选择，并证明其正确性就成了贪心算法的核心。
例题 1：POJ 4110 圣诞老人的礼物
思路：
思路非常简单，由于糖果可以任意散装组合，所以一定可以放入所有糖果或者超过超过驯鹿能够承受的重量，因此放入的总重量是确定的，只需依次放入单位重量价值高的糖果就行了，将糖果按照单位重量价值从高到低排序，依次放入，直到放满或放完为止。显然这样的方案可以证明是最优的。假设最后有单位价值更高的糖果剩余，那么将其与已经装入的单位价值低的糖果交换，就可以得到更优的解。由于在对所有糖果进行排序之后，只用对糖果进行线性遍历，因此总的算法时间复杂度为[公式]。
代码：
对比分析：
将这个题与简单的 0-1 背包问题进行对比，我们发现，二者的区别在于：0-1 背包问题中，物品是不能拆分的，也就是说物品的重量是固定的，所以我们如果用贪心的方法，按照单位重量价值最大的顺序选择装进背包的物品，无法保证得到的结果是全局最优的；而在这道问题中，因为物品是可以拆分的，所有我们其实可以把问题简化成全部为单位重量的物品，自然而然就是贪心选择了。
例题 2：Leetcode 55 跳跃游戏
思路一：
这道题最容易想到的是动态规划的思想，我们用布尔类型 dp[i] 表示从位置 i 出发否到达终点，很容易想到，如果在位置 i 处的最大跨度为 nums[i] ; 则有如下初始状态:
dp[n-1]=true
当 i 为 n-2 到 0 时，如果[公式] 或者从 [i+1,i+nums[i]] 任一位置出发可以到达末尾，则 dp[i]=true；
按照上面的思路，会有两重循环，外层循环 O(n)，内层循环 O(nums[i])，所以最坏情况下的时间复杂度为 O(sum(num))。
代码一：
思路二：
上面的过程时间复杂度比较高，事实上，我们可以将时间复杂度降低。我们从末尾开始超前遍历，依次记录当前能到达终点的最小下标 needed (初始值为 n-1)。如果我们从某一个点 i （[公式] 恒成立） 出发能够到达 [公式] ，即： [公式] ，则我们更新 needed 为 i。如果从起始点出发能到终点，则最终一定有 needed 为 0。
上面方法的时间复杂度为 O(n)。
代码二：
思路三：
还有另外一个思路，我们用 current_max 记录我们从起始点出发所能到达的最远位置；
初始时 current_max = 0, 我们从起始点开始，逐渐往后遍历，不断更新其所能到达的最远位置；
代码三：
例题 3：POJ 2287 田忌赛马
非常有趣的游戏！！看看你够不够聪明？？
田忌的马必胜，则让其胜得最有价值，就是赢齐王最快；
田忌的马必输，则让其输得最有价值，就是输给齐王最快的马；
齐王的马必胜，则让其赢得最没有价值，就用最慢的和齐王比；
齐王的马必输，则让其输得最没有价值，就用最慢的马去赢齐王的马；
思路一：
代码一：
上面的思路是从最慢的马开始看，其实我们可以从最快的马开始分类讨论，是一个近似镜像的过程。过程和代码如下：
思路二：
代码二：
课后习题：
Leetcode 455 分发饼干
Leetcode 605 种花问题
Leetcode 678 有效的括号字符串
热门标签
