贪心算法|Greedy Algorithms(背包问题)

贪心算法是一种用于优化问题的简单、直观的算法。该算法在寻找整体最优解的过程中，每一步都进行最优选择。贪心算法在一些问题上是非常成功的，例如用于压缩数据的霍夫曼编码，或者用于通过图寻找最短路径的Dijkstra算法。然而，在许多问题中，贪婪策略并不能产生最优解。

例如，在下面的动画中，贪心算法寻找和最大的路径。它通过在每个步骤中选择最大的可用数量来实现这一点。然而，贪心算法不能找到最大的和，因为它只根据每一步的信息做出决策，而不考虑整体问题。

贪心算法以达到最大和为目标，在每一步都会选择看起来是最优的即时选择，所以在第二步会选择12而不是3，不会得到包含99的最优解

贪心算法

贪心算法的结构

不同算法的背包问题，贪心算法获取特定问题中的所有数据，然后设置规则，在算法的每个步骤中为其中的元素添加到解决方案中。在上面的动画中，数据集是图中的所有数字，规则是在图的每一层选择可用的最大数字。算法构建的解是所有这些选项的和。

如果下面两个属性都为真，则可以使用贪心算法来解决这个问题。

贪心选择属性:通过每一步的最优选择，可以得到全局(全局)最优解。

最优子结构:如果整个问题的最优解包含子问题的最优解，则问题具有最优子结构。

换句话说，贪心算法处理的问题是这样的，每一步都有一个最优的选择，直到这一步，最后一步之后，算法产生整个问题的最优解。要生成贪婪算法，需要在问题中确定最优子结构或子问题。然后，确定解决方案将包括什么(例如，最大和、最短路径等)。创建某种迭代方法来遍历所有子问题并构建解决方案。

贪心算法的局限性

贪心算法有时不能找到全局最优解，因为它们没有考虑所有的数据。贪心算法所做的选择可能取决于它目前所做的选择，但它不知道自己将来可能做出的选择。

01背包贪心算法。在下面的图中，一个贪心算法试图找到图中最长的路径(每个节点内的数字占总长度的一部分)。为此，它在算法的每个步骤中选择最大的数。通过对图形的快速可视化检查，很明显，这个算法不会得到正确的解。正确的解决方案是什么?为什么贪心算法不适合这个问题?

图中最长路径的正确解是7,3,1,99。这对我们来说很清楚，因为我们可以看到没有其他节点的组合接近于99的和，所以无论我们选择哪条路径，我们都知道路径中应该有99。只有一个选项包括99:7,3,1,99。

贪心算法不能解决这个问题，因为它只根据当时最好的答案来做决定:每一步它都选择了最大的数。然而，由于可能有一些巨大的数字算法还没有看到，它可能最终选择的路径不包括这个巨大的数字。求最大和或最长路径的子问题的解不一定出现在整个问题的解中。最优子结构和贪心选择属性在这类问题中不成立。

例子

在这里，我们将研究背包问题的一种形式。背包问题涉及到，如果您想优化某些值，那么应该从一组项中选择哪些项的子集:可能是项的价值、项的大小，或者值与大小的比值。在这个问题中，我们将假设我们要么接受一个项目，要么放弃它(我们不能接受一个项目的一部分)。我们还将假设每个项目中只有一个。我们的背包大小是固定的，我们想要优化我们所带物品的价值，所以我们必须谨慎选择我们所带的物品。

我们的背包最多能装25个单位的空间。这是物品清单和它们的价值。

贪心法求解背包问题，

那么我们应该如何选择呢？

我们可以提出两种贪婪算法来解决这个问题。一个规则在每一步选择价格最大的商品，另一个规则在每一步选择最小的商品。

最大价格算法:首先，我们以笔记本电脑为例。我们获得了12个单位的价值，但现在只能在背包中携带25 - 22=3个单位的额外空间。因为包里装不下剩下的东西，所以我们只能带上笔记本电脑，最终价值总值12。

最小尺寸的项目算法:在第一步，我们将采取最小尺寸的项目:篮球。这给了我们6个单位的价值，剩下25 - 7=18个单位的空间。接下来，我们选择下一个最小的项目，课本。这就得到6+9=15个单位的价值，剩下18 - 9=9个单位的空间。由于没有剩余的项目是9个单位的空间或更少，我们不能采取更多的项目。

贪心算法的解给出了12单位价值和15单位价值。但这两个都不是最优解。亲自检查表，看看是否可以确定更好的选项。

贪心算法模型、拿Textbook和PlayStation来说，9+9=18个单位的价值，10+9=19个单位的空间。这是最优解，我们可以看出贪心算法不能解决背包问题，因为贪心选择和最优子结构性质不成立。

在贪婪算法失败的问题中，动态规划可能是一种更好的方法。

应用程序

贪心算法有很多应用。下面简要解释一下著名的图搜索算法Dijkstra算法的贪心本质

Dijkstra算法

Dijkstra算法用于求图中节点之间的最短路径。算法保存一组未访问的节点，并计算给定节点到另一个节点的临时距离。如果算法找到了到达给定节点的较短路径，则更新路径以反映较短的距离。这个问题有令人满意的优化子结构，因为如果A连接到B, B连接到C，并且路径必须经过A和B才能到达目的地C，那么从A到B的最短路径和从B到C的最短路径必须是A到C的最短路径的一部分，所以子问题的最优解是对整个问题的最优解的贡献。这是因为算法跟踪可能的任何给定节点的最短路径。

Dijkstra算法寻找a和b之间的最短路径，选取距离最小的未访问顶点，通过它计算到每个未访问节点的距离，如果节点之间的距离更小，则更新访问节点的距离。访问节点之后(设置为红色)。

Huffman编码

算法 背包问题、Huffman编码是贪心算法成功的另一个例子。哈夫曼算法分析消息，根据消息中使用的字符的频率，为每个符号分配一个可变长度编码。较常用的符号编码较短，而较少见的符号编码较长。

Huffman编码算法接收关于特定符号出现频率或概率的信息。它开始自底向上构建前缀树，从列表中最不可能的两个符号开始。它接受这些符号并形成包含它们的子树，然后从列表中删除单个符号。该算法对子树中元素的概率进行求和，并将子树及其概率添加到列表中。接下来，算法搜索列表并选择概率最小的两个符号或子树。它使用这些来生成一个新的子树，从列表中删除原始的子树/符号，然后将新的子树及其组合概率添加到列表中。这样重复，直到有一个树并添加了所有元素。在每个子树中，为每个符号创建最优编码，并共同构成整个最优编码

原文链接：greedy-algorithm

题目集：greedy-algorithms

背包问题 贪心。