Python 数据结构和算法实用指南（四）（2）-阿里云开发者社区

Python 数据结构和算法实用指南（四）（1）https://developer.aliyun.com/article/1507636

好后缀启发式

坏字符启发式并不总是提供良好的建议。Boyer-Moore 算法还使用好后缀启发式来将模式移位到文本字符串上，以找出匹配模式的位置。

好后缀启发式是基于匹配的后缀。在这里，我们将模式向右移动，以使匹配的后缀子模式与模式中另一个相同后缀的出现对齐。它的工作原理是：我们从右到左开始比较模式和文本字符串。如果我们找到任何不匹配，那么我们检查到目前为止已经匹配的后缀的出现。这被称为好后缀。我们以这样的方式移动模式，以便将好后缀的另一个出现对齐到文本上。好后缀启发式主要有两种情况：

匹配的后缀在模式中有一个或多个出现。
匹配后缀的某部分存在于模式的开头（这意味着匹配后缀的后缀存在于模式的前缀中）。

让我们通过以下示例了解这些情况。假设我们有一个模式acabac。我们对字符a和b进行不匹配，但此时，我们已经匹配了后缀，即ac。现在，我们在模式中搜索好后缀ac的另一个出现，并通过对齐后缀来移动模式，如下所示：

让我们考虑另一个例子，我们有两个选项来对齐模式的移位，以便获得两个好后缀字符串。在这里，我们将选择1来通过考虑具有最小移位的选项来对齐好后缀，如下所示：

让我们再看一个例子。在这里，我们得到了aac的后缀匹配，但对于字符b和a，我们得到了不匹配。我们搜索好后缀aac，但在模式中找不到另一个出现。但是，我们发现模式开头的前缀ac与整个后缀不匹配，但与匹配后缀aac的后缀ac匹配。在这种情况下，我们通过将模式与后缀对齐来移动模式，如下所示：

另一个好后缀启发式的案例如下。在这种情况下，我们匹配后缀aac，但在字符b和a处不匹配。我们尝试在模式中搜索匹配的后缀，但在模式中没有后缀的出现，所以在这种情况下，我们将模式移位到匹配的后缀之后，如下所示：

我们通过坏字符启发式和好后缀启发式给出的更长距离来移动模式。

Boyer-Moore 算法在模式的预处理中需要O(m)的时间，进一步搜索需要O(mn)的时间复杂度。

实现 Boyer-Moore 算法

让我们了解 Boyer-Moore 算法的实现。最初，我们有文本字符串和模式。在初始化变量之后，我们开始使用 while 循环，该循环从模式的最后一个字符开始与文本的相应字符进行比较。

然后，通过使用嵌套循环从模式的最后一个索引到模式的第一个字符，从右到左比较字符。这使用range(len(pattern)-1, -1, -1)。

外部 while 循环跟踪文本字符串中的索引，而内部 for 循环跟踪模式中的索引位置。

接下来，我们开始使用pattern[j] != text[i+j]来比较字符。如果它们不匹配，我们将使标志变量False，表示存在不匹配。

现在，我们通过使用条件j == len(pattern)-1来检查好后缀是否存在。如果这个条件为真，意味着没有可能的好后缀，所以我们检查坏字符启发式，即如果模式中存在或不存在不匹配的字符，使用条件text[i+j] in pattern[0:j]，如果条件为真，则意味着坏字符存在于模式中。在这种情况下，我们使用i=i+j-pattern[0:j].rfind(text[i+j])将模式移动到与模式中此字符的其他出现对齐。这里，(i+j)是坏字符的索引。

如果坏字符不在模式中（它不在else部分），我们使用索引i=i+j+1将整个模式移动到不匹配的字符旁边。

接下来，我们进入条件的else部分，检查好后缀。当我们发现不匹配时，我们进一步测试，看看我们的模式前缀中是否有任何好后缀的子部分。我们通过使用以下条件来做到这一点：

text[i+j+k:i+len(pattern)] not in pattern[0:len(pattern)-1]

此外，我们检查好后缀的长度是否为1。如果好后缀的长度为1，我们不考虑这个移动。如果好后缀大于1，我们通过好后缀启发式找出移动次数，并将其存储在gsshift变量中。这是将模式移动到与文本的好后缀匹配的位置的指令。此外，我们计算由于坏字符启发式可能的移动次数，并将其存储在bcshift变量中。当坏字符存在于模式中时，可能的移动次数是i+j-pattern[0:j].rfind(text[i+j])，当坏字符不在模式中时，可能的移动次数将是i+j+1。

接下来，我们通过使用坏字符和好后缀启发式的最大移动次数将模式移动到文本字符串上。最后，我们检查标志变量是否为True。如果为True，这意味着找到了模式，并且匹配的索引已存储在matched_indexes变量中。

Boyer-Moore 算法的完整实现如下所示：

text= "acbaacacababacacac"
pattern = "acacac"
matched_indexes = []
i=0
flag = True
while i<=len(text)-len(pattern):
    for j in range(len(pattern)-1, -1, -1): #reverse searching
        if pattern[j] != text[i+j]:
            flag = False #indicates there is a mismatch
            if j == len(pattern)-1: #if good-suffix is not present, we test bad character 
                if text[i+j] in pattern[0:j]:
                    i=i+j-pattern[0:j].rfind(text[i+j]) #i+j is index of bad character, this line is used for jumping pattern to match bad character of text with same character in pattern
                else:
                    i=i+j+1 #if bad character is not present, jump pattern next to it
            else:
                k=1
                while text[i+j+k:i+len(pattern)] not in pattern[0:len(pattern)-1]: #used for finding sub part of a good-suffix
                    k=k+1
                if len(text[i+j+k:i+len(pattern)]) != 1: #good-suffix should not be of one character
                    gsshift=i+j+k-pattern[0:len(pattern)-1].rfind(text[i+j+k:i+len(pattern)]) #jumps pattern to a position where good-suffix of pattern matches with good-suffix of text
                else:
                    #gsshift=i+len(pattern)
                    gsshift=0 #when good-suffix heuristic is not applicable, we prefer bad character heuristic
                if text[i+j] in pattern[0:j]:
                    bcshift=i+j-pattern[0:j].rfind(text[i+j]) #i+j is index of bad character, this line is used for jumping pattern to match bad character of text with same character in pattern
                else:
                    bcshift=i+j+1
                i=max((bcshift, gsshift))
            break
    if flag: #if pattern is found then normal iteration
        matched_indexes.append(i)
        i = i+1
    else: #again set flag to True so new string in text can be examined
        flag = True
print ("Pattern found at", matched_indexes)

总结

在本章中，我们已经讨论了在实时场景中具有广泛应用的最流行和重要的字符串处理算法。我们从查看与字符串相关的基本概念和定义开始了本章。接下来，我们详细描述了用于模式匹配问题的暴力、Rabin-Karp、KMP 和 Boyer-Moore 模式匹配算法。我们已经看到，暴力模式匹配算法非常慢，因为它逐个比较模式和文本字符串的字符。

在模式匹配算法中，我们试图找到跳过不必要比较的方法，并尽快将模式移动到文本上，以快速找到匹配模式的位置。KMP 算法通过查看模式本身中的重叠子字符串来找出不必要的比较，以避免不重要的比较。此外，我们讨论了 Boyer-Moore 算法，在文本和模式很长时非常高效。这是实践中使用的最流行的模式匹配算法。

在下一章中，我们将更详细地讨论数据结构设计策略和技术。

第十三章：设计技术和策略

在本章中，我们退一步，关注计算机算法设计中更广泛的主题。随着编程经验的增长，某些模式开始变得明显。算法的世界包含了大量的技术和设计原则。掌握这些技术是解决该领域更难问题所必需的。

在本章中，我们将讨论不同类型算法的分类方式。将描述和说明设计技术。我们还将进一步讨论算法分析。最后，我们将提供一些非常重要算法的详细实现。

本章将涵盖以下主题：

算法的分类
各种算法设计方法
各种重要算法的实现和解释

技术要求

本章使用的源代码可在以下 GitHub 链接中找到：

github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-3.7-Second-Edition/tree/master/Chapter13。

算法的分类

基于算法设计的目标，有许多分类方案。在之前的章节中，我们实现了各种算法。要问的问题是：这些算法是否具有相同的形式或相似之处？如果答案是肯定的，那么问：作为比较基础使用的相似之处和特征是什么？如果答案是否定的，那么这些算法能否被分成类别？

这些是我们将在随后的小节中讨论的问题。这里我们介绍了分类算法的主要方法。

按实现分类

将一系列步骤或流程翻译成工作算法时，可能采用多种形式。算法的核心可能使用以下一个或多个资产。

递归

递归算法是指调用自身以重复执行代码直到满足某个条件的算法。有些问题通过递归实现它们的解决方案更容易表达。一个经典的例子是汉诺塔。

简单来说，迭代函数是循环执行代码的一部分，而递归函数是调用自身来重复执行代码的函数。另一方面，迭代算法使用一系列步骤或重复结构来制定解决方案；它迭代执行代码的一部分。

这种重复结构可以是一个简单的while循环，或者任何其他类型的循环。迭代解决方案也比递归实现更容易想到。

逻辑

算法的一种实现是将其表达为受控逻辑推导。这个逻辑组件由将在计算中使用的公理组成。控制组件确定了推导应用到公理的方式。这表达为形式 algorithm = logic + control。这构成了逻辑编程范式的基础。

逻辑组件决定了算法的含义。控制组件只影响其效率。在不修改逻辑的情况下，可以通过改进控制组件来提高效率。

串行或并行算法

大多数计算机的 RAM 模型允许假设计算是一次执行一条指令的。

串行算法，也称为顺序算法，是按顺序执行的算法。执行从开始到结束进行，没有其他执行过程。

为了能够同时处理多条指令，需要不同的模型或计算技术。并行算法可以同时执行多个操作。在 PRAM 模型中，有共享全局内存的串行处理器。处理器还可以并行执行各种算术和逻辑操作。这使得可以同时执行多条指令。

并行/分布式算法将问题分解成子问题，分配给处理器来收集结果。一些排序算法可以有效地并行化，而迭代算法通常是可并行化的。

确定性与非确定性算法

确定性算法每次以相同的输入运行时都会产生相同的输出。有一些问题的解决方案设计非常复杂，以至于以确定性的方式表达它们的解决方案可能是一个挑战。

非确定性算法可以改变执行顺序或某些内部子过程，导致每次运行算法时最终结果都会发生变化。

因此，每次运行非确定性算法时，算法的输出都会不同。例如，使用概率值的算法将根据生成的随机数的值，在连续执行时产生不同的输出。

按复杂度分类

确定算法的复杂度是为了估计在计算或程序执行期间需要多少空间（内存）和时间。通常，通过它们的复杂度来比较两个算法的性能。较低复杂度的算法，即执行给定任务所需的空间和时间较少的算法，更受青睐。

第三章《算法设计原理》更全面地介绍了复杂性。我们将在这里总结我们所学到的内容。

复杂度曲线

让我们考虑一个规模为 n 的问题。为了确定算法的时间复杂度，我们用 T(n)表示。该值可能属于 O(1)、O(log n)、O(n)、O(n log(n))、O(n²)、O(n³)或 O(2^n)。根据算法执行的步骤，时间复杂度可能会受到影响。符号 O(n)捕捉了算法的增长率。

让我们现在来考虑一个实际的场景，来确定哪种算法更适合解决给定的问题。我们如何得出冒泡排序算法比快速排序算法慢的结论？或者，一般来说，我们如何衡量一个算法相对于另一个算法的效率？

好吧，我们可以比较任意数量的算法的大 O 来确定它们的效率。这种方法给我们提供了一个时间度量或增长率，它描述了算法在 n 变大时的行为。

这是一个图表，显示了算法性能可能属于的不同运行时间：

按照从最好到最差的顺序，运行时间的列表为 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(n³)和 O(2^n)。因此，如果一个算法的时间复杂度为 O(1)，而另一个算法的复杂度为 O(log n)，应该选择第一个算法。

按设计分类

在本节中，我们根据它们的设计提出了算法的分类。

一个给定的问题可能有多种解决方案。当分析这些解决方案时，可以观察到每个解决方案都遵循某种模式或技术。我们可以根据它们解决问题的方式对算法进行分类，如下面的小节所示。

分而治之

这种问题解决方法正如其名称所示。为了解决（征服）某个问题，算法将其分解为可以轻松解决的子问题。此外，这些子问题的解决方案被组合在一起，以便最终解决方案是原始问题的解决方案。

问题被分解为更小的子问题的方式大多是通过递归完成的。我们将在随后的小节中详细讨论这种技术。使用这种技术的一些算法包括归并排序、快速排序和二分查找。

动态规划

这种技术与分而治之类似，即将问题分解为更小的问题。然而，在分而治之中，必须先解决每个子问题，然后才能用其结果来解决更大的问题。

相比之下，动态规划不会计算已经遇到的子问题的解决方案。相反，它使用一种记忆技术来避免重新计算。

动态规划问题具有两个特征——最优子结构和重叠子问题。我们将在下一节进一步讨论这一点。

贪婪算法

确定某个问题的最佳解决方案可能会非常困难。为了克服这一点，我们采用一种方法，从多个可用选项或选择中选择最有前途的选择。

使用贪婪算法，指导规则是始终选择产生最有利的结果的选项，并继续这样做，希望达到完美的解决方案。这种技术旨在通过一系列局部最优选择找到全局最优的最终解决方案。局部最优选择似乎导致解决方案。

技术实现

让我们深入讨论一些我们讨论过的理论编程技术的实现。我们从动态规划开始。

使用动态规划进行实现

正如我们已经描述的，在这种方法中，我们将给定的问题分解为更小的子问题。在找到解决方案时，要注意不要重新计算任何先前遇到的子问题。

这听起来有点像递归，但这里有些不同。一个问题可能适合使用动态规划来解决，但不一定需要形成递归调用的形式。

使问题成为动态规划的理想候选者的一个特性是它具有重叠的子问题集。

一旦我们意识到在计算过程中子问题的形式已经重复，我们就不需要再次计算它。相反，我们返回先前遇到的子问题的预先计算结果。

为了确保我们永远不必重新评估子问题，我们需要一种有效的方法来存储每个子问题的结果。以下两种技术是 readily available。

记忆化

这种技术从初始问题集开始，将其分解为小的子问题。在确定了子程序的解决方案之后，我们将结果存储到该特定子问题中。将来，当遇到这个子问题时，我们只返回其预先计算的结果。

制表

在制表中，我们填充一个表格，其中包含子问题的解决方案，然后将它们组合起来解决更大的问题。

斐波那契数列

让我们考虑一个例子来理解动态规划的工作原理。我们使用斐波那契数列来说明记忆化和制表技术。

斐波那契数列可以使用递推关系来演示。递推关系是用来定义数学函数或序列的递归函数。例如，以下递推关系定义了斐波那契数列[1, 1, 2, 3, 5, 8 …]：

func(1) = 1
func(0) = 1 
func(n) = func(n-1) + func(n-2)

请注意，斐波那契数列可以通过将n的值放入序列[1, 2, 3, 4, …]来生成。

记忆化技术

让我们生成斐波那契数列的前五项：

1 1 2 3 5

生成序列的递归式程序如下：

def fib(n): 
    if n <= 2: 
       return 1 
    else: 
       return fib(n-1) + fib(n-2)

代码非常简单，但由于递归调用的存在，读起来有点棘手，因为最终解决了问题。

当满足基本情况时，fib()函数返回 1。如果n等于或小于 2，则满足基本情况。

如果未满足基本情况，我们将再次调用fib()函数，并这次将第一个调用提供n-1，第二个提供n-2：

return fib(n-1) + fib(n-2)

解决斐波那契数列中的第i^(th)项的策略布局如下：

对树状图的仔细观察显示了一些有趣的模式。对**fib(1)的调用发生了两次。对fib(2)的调用发生了三次。此外，对fib(3)**的调用发生了两次。

相同函数调用的返回值永远不会改变；例如，每当我们调用**fib(2)**时，其返回值始终相同。**fib(1)和fib(3)**也是如此。因此，如果我们每次遇到相同的函数时都重新计算，将浪费计算时间，因为返回的结果相同。

对具有相同参数和输出的函数的重复调用表明存在重叠。某些计算在较小的子问题中重复出现。

更好的方法是在首次遇到fib(1)时存储计算结果。同样，我们应该存储fib(2)和fib(3)的返回值。稍后，每当我们遇到对fib(1)、**fib(2)或fib(3)**的调用时，我们只需返回它们各自的结果。

我们的fib调用的图现在看起来像这样：

如果多次遇到，我们已经消除了计算fib(3)，fib(2)和**fib(1)**的需要。这是备忘录技术的典型，其中在将问题分解为子问题时，不会重新计算重叠调用函数。

我们斐波那契示例中的重叠函数调用是fib(1)、fib(2)和fib(3)：

def dyna_fib(n, lookup): 
        if n <= 2: 
            lookup[n] = 1 
        if lookup[n] is None: 
            lookup[n] = dyna_fib(n-1, lookup) + dyna_fib(n-2, lookup) 
        return lookup[n]

要创建一个包含 1,000 个元素的列表，我们执行以下操作，并将其传递给dyna_fib函数的 lookup 参数：

map_set = [None]*(1000)

这个列表将存储对dyna_fib()函数的各种调用的计算值：

if n <= 2: 
        lookup[n] = 1

对于dyna_fib()函数的任何小于或等于 2 的n的调用都将返回 1。当评估dyna_fib(1)时，我们将值存储在map_set的索引 1 处。

将lookup[n]的条件写为以下内容：

if lookup[n] is None:
    lookup[n] = dyna_fib(n-1, lookup) + dyna_fib(n-2, lookup)

我们传递 lookup，以便在评估子问题时可以引用它。对dyna_fib(n-1, lookup)和dyna_fib(n-2, lookup)的调用存储在lookup[n]中。

当我们运行函数的更新实现以找到斐波那契数列的第*i*^(th)项时，我们可以看到显着的改进。这个实现比我们最初的实现运行得快得多。将值 20 提供给这两个实现，并观察执行速度的差异。

然而，由于使用额外的内存存储函数调用的结果，更新后的算法牺牲了空间复杂度。

表格法

动态规划中的第二种技术涉及使用结果表或在某些情况下使用矩阵来存储计算结果以供以后使用。

这种方法通过首先解决最终解决方案的路径来解决更大的问题。对于fib()函数，我们开发了一个表，其中预先确定了fib(1)和fib(2)的值。基于这两个值，我们将逐步计算fib(n)：

def fib(n): 
        results = [1, 1] 
        for i in range(2, n): 
            results.append(results[i-1] + results[i-2]) 
        return results[-1]

results变量在索引 0 和 1 处存储值 1 和 1。这代表fib(1)和fib(2)的返回值。要计算大于 2 的值的fib()函数的值，我们只需调用for循环，将results[i-1] + results[i-2]的和附加到结果列表中。

使用分治法实现

这种编程方法强调将问题分解为与原始问题相同类型或形式的较小子问题的需要。这些子问题被解决并组合以获得原始问题的解决方案。

以下三个步骤与这种编程相关。

划分

划分意味着分解实体或问题。在这里，我们设计手段将原始问题分解为子问题。我们可以通过迭代或递归调用来实现这一点。

征服

无法无限地继续将问题分解为子问题。在某个时候，最小的不可分割问题将返回一个解决方案。一旦这种情况发生，我们可以扭转我们的思维过程，并说如果我们知道最小子问题的解决方案，我们就可以获得原始问题的最终解决方案。

合并

为了得到最终解决方案，我们需要结合较小问题的解决方案来解决更大的问题。

还有其他变体的分而治之算法，例如合并和组合，征服和解决。许多算法使用分而治之原则，例如归并排序、快速排序和 Strassen 矩阵乘法。

我们现在将描述归并排序算法的实现，就像我们在第三章“算法设计原理”中看到的那样。

归并排序

归并排序算法基于分而治之的原则。给定一列未排序的元素，我们将列表分成两个近似的部分。我们继续递归地将列表分成两半。

经过一段时间，由于递归调用而创建的子列表将只包含一个元素。在那时，我们开始在征服或合并步骤中合并解决方案：

def merge_sort(unsorted_list): 
        if len(unsorted_list) == 1: 
            return unsorted_list 
        mid_point = int((len(unsorted_list))//2) 
        first_half = unsorted_list[:mid_point] 
        second_half = unsorted_list[mid_point:] 
        half_a = merge_sort(first_half) 
        half_b = merge_sort(second_half) 
        return merge(half_a, half_b)

我们的实现从将未排序的元素列表传递到merge_sort函数开始。if语句用于建立基本情况，即如果unsorted_list中只有一个元素，我们只需再次返回该列表。如果列表中有多于一个元素，我们使用mid_point = int((len(unsorted_list)) // 2)找到近似中间位置。

使用这个mid_point，我们将列表分成两个子列表，即first_half和second_half：

first_half = unsorted_list[:mid_point] 
    second_half = unsorted_list[mid_point:]

通过将这两个子列表再次传递给merge_sort函数来进行递归调用：

half_a = merge_sort(first_half)  
    half_b = merge_sort(second_half)

现在是合并步骤。当half_a和half_b传递了它们的值后，我们调用merge函数，该函数将合并或组合存储在half_a和half_b中的两个解决方案，即列表：

def merge(first_sublist, second_sublist): 
     i = j = 0 
     merged_list = [] 
     while i < len(first_sublist) and j < len(second_sublist): 
         if first_sublist[i] < second_sublist[j]: 
             merged_list.append(first_sublist[i]) 
             i += 1 
         else: 
             merged_list.append(second_sublist[j]) 
             j += 1 
     while i < len(first_sublist): 
         merged_list.append(first_sublist[i]) 
         i += 1 
     while j < len(second_sublist): 
         merged_list.append(second_sublist[j]) 
         j += 1 
     return merged_list

merge函数接受我们要合并的两个列表first_sublist和second_sublist。i和j变量被初始化为 0，并用作指针，告诉我们在合并过程中两个列表的位置。

最终的merged_list将包含合并后的列表：

while i < len(first_sublist) and j < len(second_sublist): 
        if first_sublist[i] < second_sublist[j]: 
            merged_list.append(first_sublist[i]) 
            i += 1 
        else: 
            merged_list.append(second_sublist[j]) 
            j += 1

while循环开始比较first_sublist和second_sublist中的元素。if语句选择两者中较小的一个，first_sublist[i]或second_sublist[j]，并将其附加到merged_list。i或j索引递增以反映我们在合并步骤中的位置。当任一子列表为空时，while循环停止。

可能会有元素留在first_sublist或second_sublist中。最后两个while循环确保这些元素在返回merged_list之前被添加。

对merge(half_a, half_b)的最后调用将返回排序后的列表。

让我们通过合并两个子列表[4, 6, 8]和[5, 7, 11, 40]来对算法进行干扰运行：

步骤	`first_sublist`	`second_sublist`	`merged_list`
步骤 0	`[4 6 8]`	`[5 7 11 40]`	`[]`
步骤 1	`[ 6 8]`	`[5 7 11 40]`	`[4]`
步骤 2	`[ 6 8]`	`[ 7 11 40]`	`[4 5]`
步骤 3	`[ 8]`	`[ 7 11 40]`	`[4 5 6]`
步骤 4	`[ 8]`	`[ 11 40]`	`[4 5 6 7]`
步骤 5	`[ ]`	`[ 11 40]`	`[4 5 6 7 8]`
步骤 6	`[]`	`[ ]`	`[4 5 6 7 8 11 40]`

注意粗体文本代表循环中当前项的引用，first_sublist（使用i索引）和second_sublist（使用j索引）。

在执行的这一点上，合并函数中的第三个while循环开始将 11 和 40 移入merged_list。返回的merged_list将包含完全排序的列表。

请注意，合并算法需要O(n)的时间，而合并排序算法的运行时间复杂度为O(log n) T(n) = O(n)*O(log n) = O(n log n)。

使用贪婪算法的实现

正如我们之前讨论的，贪婪算法做出决策以产生最佳的局部解决方案，从而提供最佳解决方案。这种技术的希望是，通过在每一步做出最佳选择，总路径将导致整体最优解决方案或结束。

贪婪算法的例子包括用于查找最小生成树的Prim 算法、背包问题和旅行推销员问题。

硬币计数问题

为了演示贪婪技术的工作原理，让我们看一个例子。考虑一个问题，我们希望计算使给定金额 A 所需的最小硬币数量，其中我们有给定硬币值的无限供应。

例如，在某个任意国家，我们有以下硬币面额：1、5 和 8 GHC。给定一个金额（例如 12 GHC），我们想要找到提供这个金额所需的最少硬币数量。

使用面额{a[1],a[2],a[3]...a[n]}来提供给定金额 A 的最小硬币数量的算法如下：

我们对面额列表{a[1], a[2], a[3] ...a[n]}进行排序。
我们得到小于 A 的{a[1], a[2], a[3]...a[n]}中的最大面额。
我们通过将 A 除以最大面额来获得商。
我们通过使用（A % 最大面额）来获得剩余金额 A。
如果 A 的值变为 0，则返回结果。
否则，如果 A 的值大于 0，我们将最大面额和商变量附加到结果变量中。并重复步骤 2-5。

使用贪婪方法，我们首先选择可用面额中的最大值——8——来除以 12。余数 4 既不能被 8 整除，也不能被比 8 更小的面额 5 整除。所以，我们尝试 1 GHC 面额的硬币，需要四个。最终，使用这种贪婪算法，我们返回了一个 8 GHC 硬币和四个 1 GHC 硬币的答案。

到目前为止，我们的贪婪算法似乎表现得相当不错。返回相应面额的函数如下：

def basic_small_change(denom, total_amount): 
        sorted_denominations = sorted(denom, reverse=True) 
        number_of_denoms = [] 
        for i in sorted_denominations: 
            div = total_amount // i 
            total_amount = total_amount % i 
            if div > 0: 
                number_of_denoms.append((i, div)) 
        return number_of_denoms

这种贪婪算法总是从可能的最大面额开始。注意denom是一个面额列表，sorted(denom, reverse=True)会将列表按照相反的顺序排序，这样我们就可以在索引0处获得最大面额。现在，从排序后的面额列表sorted_denominations的索引0开始，我们迭代并应用贪婪技术：

for i in sorted_denominations: 
        div = total_amount // i 
        total_amount = total_amount % i 
        if div > 0: 
            number_of_denoms.append((i, div))

循环将遍历面额列表。每次循环运行时，它通过将total_amount除以当前面额i来获得商div。total_amount变量被更新以存储余数以供进一步处理。如果商大于 0，我们将其存储在number_of_denoms中。

然而，有一些可能的情况下这种算法可能会失败。例如，当传入 12 GHC 时，我们的算法返回了一个 8 GHC 和四个 1 GHC 硬币。然而，这个输出并不是最优解。最佳解是使用两个 5 GHC 和两个 1 GHC 硬币。

这里提出了一个更好的贪婪算法。这次，函数返回一个允许我们调查最佳结果的元组列表：

def optimal_small_change(denom, total_amount): 
        sorted_denominations = sorted(denom, reverse=True) 
        series = [] 
        for j in range(len(sorted_denominations)): 
            term = sorted_denominations[j:] 
            number_of_denoms = [] 
            local_total = total_amount 
            for i in term: 
                div = local_total // i 
                local_total = local_total % i 
                if div > 0: 
                    number_of_denoms.append((i, div)) 
            series.append(number_of_denoms) 
        return series

外部for循环使我们能够限制我们找到解决方案的面额：

for j in range(len(sorted_denominations)): 
        term = sorted_denominations[j:] 
        ...

假设我们有列表[5, 4, 3]，在sorted_denominations中对其进行切片[j:]有助于我们获得子列表[5, 4, 3]，[4, 3]和[3]，从中我们尝试找到正确的组合。

Python 数据结构和算法实用指南（四）（3）https://developer.aliyun.com/article/1507647

Python 数据结构和算法实用指南（四）（2）