贪心算法通过在每一步做出最佳选择来解决问题。它不会着眼于所有可能的解决方案，而是专注于当下看起来最好的选项。
!fractional-knapsack贪心算法示例 – 分数背包问题
问题结构：
大多数适用贪心算法的问题都遵循以下两个性质：
1). 贪心选择性质： 这一性质指出，在每一步选择最佳可能的选项将导向最佳的整体解决方案。如果这一点不成立，贪心方法可能就不适用。
2). 最优子结构： 这意味着我们可以将问题分解成更小的部分，并且通过做出贪心选择来解决这些小问题，有助于解决整体问题。
如何识别贪心问题：
主要有两种方法来识别贪心问题 –
1). 我们可以将问题分解成更小的部分吗？ 如果可以，并且解决这些部分有助于我们解决主问题，那么它很可能可以用贪心方法来解决。例如 – 在活动选择问题中，一旦我们选择了一个活动，剩下的子问题就是选择那些在选定活动之后开始的活动。
2). 在每一步选择最佳选项会导向最佳的整体解决方案吗？ 如果答案是肯定的，那么贪心算法可能是一个不错的选择。例如 – 在 Dijkstra 最短路径算法中，每一步选择最小成本的边保证了最短路径。
贪心算法与动态规划的区别：
1). 贪心算法在问题具有贪心选择性质和最优子结构时有效，而动态规划虽然在问题具有最优子结构时也有效，但它还需要重叠子问题。
2). 在贪心算法中，每一个局部决策都会导向整个问题的最优解；而在动态规划中，主问题的解依赖于这些重叠子问题。
解决贪心问题的一些常用方法：
1). 排序
作业排序:- 为了最大化利润，我们将优先考虑利润更高的作业。因此，我们根据利润按降序对它们进行排序 。对于每个作业，我们尝试尽可能晚地将其安排在截止期限内，以便为其他截止期限更近的作业留出更早的时间段。
活动选择:- 为了最大化不重叠活动的数量，我们优先考虑结束更早的活动，这有助于我们选择更多的活动。因此，我们根据它们的结束时间按升序对它们进行排序 。然后，我们选择第一个活动，并继续添加在之前活动结束后开始的后续活动。
不相交区间:- 这个问题的方法与前一个完全相似，我们根据区间的开始或结束时间按升序排序。然后，选择第一个区间，并继续添加在上一个区间结束后开始的下一个区间。
分数背包问题:- 基本思路是计算每个物品的利润/重量比率，并基于此比率对物品进行排序。然后取出比率最高的物品，并尽可能多地添加它（可以是整个元素或者是它的一部分）。
Kruskal 算法:- 为了找到最小生成树 (MST)，我们优先考虑权重最小的边，以最小化总成本。我们首先根据权重按升序对所有边进行排序。然后，我们迭代地将边添加到 MST 中，同时确保添加边不会形成环。
2). 使用优先队列或堆
Dijkstra 算法:- 为了找到从源节点到图中所有其他节点的最短路径，我们根据与源节点的最小距离对节点进行优先排序。我们首先初始化距离并使用一个最小优先队列。在每次迭代中，我们从优先队列中提取距离最小的节点，并更新其相邻节点的距离。这个过程一直持续到处理完所有节点，确保我们高效地找到最短路径。
连接 N 条绳子:- 在这个问题中，最先选取的绳子长度会在总成本中被计算多次。因此，策略是在每一步连接最短的两条绳子并重复此过程。